Guan

Guan (to observe in Mandarin) is a general-purpose logic programming system written in C# and built as a .NET Standard Library. It has been tested in both Windows and Linux environments.

Guan employs Prolog style syntax for writing logic rules. It enables easy interop between such rules with regular C# code and the vast .NET Base Class Library. External Predicates are written in C# and logic rules can be housed in simple text files or as string variables in your consuming program. These logic rules will be parsed and executed by Guan, which provides imperative, procedural, and even functional programming idioms the expressive power of logic programming for use in several novel contexts, not the least of which is Configuration-as-Logic.

Guan is not 100% like Prolog today (nor is that the goal). You are welcome to help Guan get there, of course. For now, if you write .NET code, then Guan provides you with another familiar and convenient way to add logic programing to your .NET programs.

Author: Lu Xun, Microsoft.

Getting Started

Please see the Getting Started section to play around with Guan in a sample application, GuanExamples, with very simple rules, simple External Predicate implementations, and highly documented sample code. It is assumed that you are already familiar with logic programming.

Syntax

As stated above, Guan uses Prolog style syntax. We will not describe things that are common with standard Prolog, but rather present the differences below (they are different mostly to allow more natural interop between rules and C# code):

• The trailing '.' is not required as a delimiter for Guan logic rules as every rule is represented in a separate string. However, you could employ the trailing "." for use in delimiting rules in a file that contains multiple rules (and rules that contain complex logic or multiple sub rules). You would then write your own pre-parser to feed the rules into a List<string>, which is what Guan expects.

• A variable must start with a '?', followed by alphanumeric characters (\w) or underscore. For example: ?a, ?A, ?_a, ?aa_ are all valid variables. Note that this is very different from Prolog where the first character must be capitalized.

• Predicate name can be any combination of alphanumeric characters and underscore. The predicate name uniquely identifies the predicate type (in standard Prolog, predicate name plus the number of argument uniquely identifies a predicate type).

• The usage of ";" for the disjunction of goals is currently not supported. Use a separate predicate type with multiple rules for disjunction.

• Use not(goal) for negation, "\+ goal" is not supported.

• The arguments of a compound term are named (alphanumeric characters and underscore). For example: TraceRecord(Source=?NodeId, GroupType=P2P.Send, text=?text, time=?t). The argument name can be omitted for the following cases:

• It is allowed to have positional arguments (like standard Prolog) before the appearance of any named argument. For example, TraceRecord(?NodeId, P2P.Send, text=?text, time=?t) is a valid compound term where the first two arguments do not have explicit names. Internally, names are assigned implicitly. The first argument will have a name "0", and the second with "1", etc. Note that the argument name "time" for the last argument can't be omitted, since there is already a named argument "text" before it.

  • If an argument is not positional (appears after some named argument), its name can be inferred from the argument value if one of the following is true:

  • If the argument is a variable, the argument name will be the same as the variable name. For example, TraceRecord(Source=?NodeId, GroupType=P2P.Send, ?text, time=?t). The name of the 3rd argument is inferred to be "text".

  • If the argument is a compound, the argument name will be the same as the functor name. For example, somegoal(arg0=0, point(1, 2)). The name of the second argument is "point".

A note on named arguments. When to use them? The most important reason to use named arguments is to support optional arguments. Only when an argument is present on both sides will unification be performed. This is a major difference compared to regular Prolog, but we believe it is very convenient for predicate authors.

• The custom behavior of a predicate type might implement type-specific syntax sugar: if the head of a rule with the corresponding type does not have an argument mentioned, the argument will be added automatically with the value being a variable with the same name. For example, suppose "mygoal" is a type which has two arguments v1 and v2, the following rules are all equivalent:

mygoal :- body 

mygoal(v1=?v1, v2=?v2) :- body 

mygoal(v1=?v1) :- body 

Function & Constraint

The functor of some compound terms can be evaluated at runtime, when all of its arguments are grounded. They can be considered as functions. For example:

add(?t1, -00:10:00) 

This is a compound term with function "add". Since "add" is built-in evaluated function, when the variable "?t1" is instantiated, the entire compound term can be evaluated to become a constant term (in this case "?t1" should be a C# DateTime object, which is added with a TimeSpan of minus 10 minutes, so we effectively are getting a timestamp that is 10 minutes earlier than "?t1").

eq(?v1, ?v2) 

This is another example. The "eq" function will check whether the two arguments are equal (using C# object.Equals), the result is a constant of C# Boolean value.

Operators are defined for some commonly used functors. Below is a list with the obvious semantics:

"||", "&&", "==", "!=", ">", ">=","<","<=","+","-","*","/" 

Evaluated compound terms can be nested. For example:

?t2 > add(?t1, -00:10:00) && ?v1 == ?v2 

This is how logical programming in Guan handles arithmetic operations and comparisons, which is quite different than standard Prolog. Since we are free to add new functions which invoke arbitrary C# logic, Guan can provide capabilities that are not possible in Prolog.

When a goal contains a function, it becomes a constraint and the goal is considered satisfied if and only if the evaluation is "True" (typically such goal should return Boolean result, but if the result is not Boolean, we treat null and empty string as False and everything else as True). If the function can't be evaluated because of un-instantiated variables, the constraint will be passed along for the remaining goals, until the variables are instantiated. If there are still variables un-instantiated when there is no more goal left in the rule, the constraint will be ignored.

Built-in Predicates (aka System Predicates)

Guan provides some standard built-in predicates. Many of them have already been described in the examples, for the others please refer to documentation for standard Prolog

assert 
! (cut) 
fail 
not 
var 
nonvar 
atom 
compound 
ground 
= (unify) 
retract

Some commonly used predicates for list related operations: 

append 
member 
length 
reverse 

Popular Prolog implementations typically have many more defined, which might be added to Guan in the future.

The below predicates are either unique to Guan, or have some special semantics:

enumerable: takes a C# collection object as the first argument and returns the members as the second argument.

forwardcut:

For temporal reasoning, an event often needs to be matched with another event that is closest to it. For example, consider a sequence of events of Start, End, Start, End, Start, Start, End… Such sequence could be the start and end of a process as an example. Note that sometimes the End event is missing, as the process could have crashed. Now suppose that we want to define a frame type ProcessStartEnd. We cannot use a simple rule like this:

ProcessStartEnd(?StartTime, ?EndTime) :- Start(time=?StartTime),
    End(time=?EndTime),
    ?EndTime > ?StartTime 

As this could match the start of a process instance with the end of a later instance. Of course, if there is a unique process id we can use, such problem can be avoided. But what if there is no such id and all we can rely on is the order of the events? One solution is to use negation as failure:

ProcessStartEnd(?StartTime, ?EndTime) :- Start(time=?StartTime), 
    End(time=?EndTime), 
    ?EndTime > ?StartTime, 
    not Between(?StartTime, ?EndTime) 

Between(?StartTime, ?EndTime) :- Start(time=?t), 
    ?t >?StartTime, 
    ?t < EndTime 

This works, but it requires the trace to be searched twice (assuming the implementation of the Start and End depends on some linear scan of trace).

Guan provides an alternative: when the Start event is found, in addition to search for the End event, we search for the next Start event in parallel. This is as if we are expanding the search tree at different levels simultaneously. Whenever the search for the Start is found, the pending search for End, if any, is cancelled. Below is the rule for this approach:

ProcessStartEnd(?StartTime, ?EndTime) :- Start(time=?StartTime),
    forwardcut,
    End(time=?EndTime), 
    ?EndTime > ?StartTime 

It is almost the same as the initial wrong version, except that a "forwardcut" goal is added, instructing the infrastructure to keep expanding the choice points for the goal before it while exploring the next goals and perform the cancellation as appropriate. Note that this is again relying on the multiplexing behavior of the parallel tasks.

In general, the sequential backtracking is a restriction of the original Prolog search mechanism and there are var