Hello again everyone!
One of the things that inspired me most to get back to blogging was my foray into a bizarre little language called Prolog. You may have heard of it, and perhaps even used it yourself, but if you don’t find it terribly fascinating, then I’m here to try and change your mind!
Programmation Logique
Prolog is defined as a declarative logic programming language by Wikipedia. This means that the fundamental building blocks of a Prolog program are declarations of truth in your program’s problem space. This is quite similar to first order logic, which tends to make Prolog a nice choice for implementing mathematical algorithms!
For example, the Fibonacci sequence can be expressed as this series:
F0 = 0
F1 = 1
Fn = Fn - 1 + Fn - 2
The corresponding Prolog code looks (somewhat) similar:
/*
* CLP(FD) stands for Constraint Logic Programming (Finite Domains).
* It's a special library that allows arithmetic operators to work
* bi-directionally. Don't worry about it too much right now.
*/
:- use_module(library(clpfd)).
fib(X,0) :- X = 0. % fib sub X is 0 IF X == 0
fib(X,1) :- X = 1. % fib sub X is 1 IF X == 1
fib(X,Result) :-
X #> 1, % IF X > 1
X1+1 #= X, fib(X1,Add1), % Get fib sub X - 1
X2+2 #= X, fib(X2,Add2), % Get fib sub X - 2
Result #= Add1 + Add2. % Result is both of those added together
The weirdest thing to get used to about Prolog syntax, in my experience, is tracing which portions of the code are intended as arguments and which are intended as outputs. The true madness of this language is: that’s an amazing expressive feature. Many Prolog functions (they’re called predicates) are written to handle both possibilities. Using the code above, I can ask for the 8th Fibonacci number by “asking” Prolog:
fib(8,Number).
And Prolog responds:
Number = 21 .
But if I want to know which number in the sequence 21 is, I can ask:
fib(Which,21).
And Prolog says:
Which = 8 .
How does Prolog do this? In SWI-Prolog, a popular Prolog implementation, we can run our query with the trace predicate to see how it goes about finding a solution. Put simply, the Prolog runtime will search for values that satisfy the given rules. Read as plain english, the Fibonacci code goes something like
fib of X is 0 if X is equal to 0
fib of X is 1 if X is equal to 1
fib of X is Result if X is greater than 1, [and] X1 is X+1, [and] fib of X1 is Add1, [and] X2 is X+2, [and] fib of X2 is Add2, [and] Result is Add1+Add2
The runtime will pick a value and test it against each of the “function definitions” until either it fails all of them, or succeeds one of them. This “guessing” allows Prolog to, in many cases, run forward and backward, but without writing any extra code.
Why Prolog?
Admittedly, Prolog is not the most pragmatic language to learn. It isn’t the backbone of the internet (though you can write servers in it), you won’t find it powering embedded systems (though special-purpose hardware was once made to run Prolog), and it won’t be in even the top 10 languages recommended for writing games (though it’s pretty good for writing AI!). Why, then, should one torment oneself learning a drastically different syntax and a unique (read: not widely applicable) programming paradigm?
It is a language with tons of possibility, but one of the most important things in software (and in life) is to choose the right tool for the job. What, then, do we do with Prolog? In my case, I was taken by the language processing possibilities that Prolog offers.
Example: The Forever Project
Ever since December 2017, I’ve been trying to do Cool Stuff™ on my tabletop app, UESRPG CharGen. For the uninitiated, that’s the app I’m constantly writing to assist my friends in our campaign of Unofficial Elder Scrolls RPG. It manages characters, skills, spells, and combat turn orders. There’s a litany of new features always begging for my attention, but the most outlandish and fascinating one in my mind is implementing “Talents”.
(Talents are special modifiers that characters can learn to spice up combat, reduce XP costs, and otherwise modify gameplay in unexpected ways.)
To tackle this issue, since the variety of available Talents in the game is so huge, I thought it might be ideal to create a domain specific language (DSL) for writing talents. That way, my players could whip up their own implementations with little friction, and I wouldn’t have to spend time translating every talent in the book to C#.
Picking the Right Tool
When researching the problem of language development, I came across an excellent series of articles on lexical analysis for the purpose of building interpreters. Author Faiçal Tchirou walks the reader through implementation of a finite state machine to tokenize inputs matching certain rules. I thought that it might be easier to compose language features if they were written as Prolog rules, conditions which can easily be strung together!
I’ve never designed a language before, but my approach was to create some sample talent scripts to sort of iron out what a natural syntax might feel like. You can read those sample scripts here. Here’s one, for example:
// The character can choose to use twice his Perception bonus for his Initiative Rating instead of the usual value
Pre InitiativeRoll {
Player Choose ( "Use 2x Perception bonus for Initiative Rating?", YesOrNo ) {
Yes: Player.InitiativeRating = Bonus(Perception) * 2;
}
}
It’s a little bit like Groovy, which leans heavily on closures, essentially lambda functions. The syntax isn’t final, especially where some of it doesn’t seem super intuitive—coming back to it after a few months leads me to question the whole “Player Choose” thing, for instance—but there is a crucial aspect here which I’m pretty confident about, and that’s the concept of a context. I’ll be taking deeper dives into my language concepts as the language develops, but for now I can give a quick treatment of contexts, since I have some Prolog code to go along with it!
Contexts, or the Working Man’s Extension Points
Instead of defining several global delegates for my players to extend with C#, I decided to fold the idea of “where the extension must execute” into my DSL. I will still be defining several delegates, but instead of:
1) looking up how to extend a particular point in gameplay 2) looking up all the necessary C# types the delegate requires as arguments 3) manually writing a delegate function 4) manually attaching that function to the extension point
the DSL will allow its users to simply say Pre Roll("Combat") { /* do stuff */ }.
To start, in Prolog, I’ve declared some context components:
/*
* A "context" has the form [Pre|Post] context_name { [actions] }
*/
context_time( 'Pre' ).
context_time( 'Post' ).
% The "Always" context_time does not take a context_name
context_time( 'Always' ).
...
/*
* The available context_names are defined below.
*/
context_name( 'InitiativeRoll' ).
context_name( 'AttackTest' ).
context_name( 'CalculateAp' ).
context_name( 'TestSkill' ).
context_name( 'TestSkillGovernedBy' ).
The ingredients for a context extension are thus: will this extension execute before or after the context, which context, and what will this extension do? Composing this in Prolog is almost as simple as stringing together context_time(When), context_name(What)!
I’ve written some handy helper predicates to pull out atoms based on my predicates above, sensibly-named pull_atom and required_whitespace. Taking those into account, here is the full code (so far) to identify context tokens:
/*
* Step through the input and attempt to find a context token.
*/
id_context( X, Token, RestOfChars ) :-
find_context_time( X, Time, NonTimeChars ),
required_whitespace( NonTimeChars, NameChars ),
find_context_name( NameChars, Name, RestOfChars ),
( context_with_args( Name ) -> % If this is a context which takes args,
% Do argument stuff
( write_ln( "Args context!" ) ) ;
( write_ln( "No args!" ) ) % Otherwise don't
),
% Todo: find the nested tokens allowed within a context
Token = token( type( 'context' ), time( Time ), name( Name ) ).
/*
* The first element of a context token is the time specifier
*/
find_context_time( X, ContextTime, UnconsumedChars ) :-
pull_atom( X, ContextTime, context_time, maxchars_context_time, UnconsumedChars ).
/*
* Time specifiers must be followed by the context name.
*/
find_context_name( X, ContextName, UnconsumedChars ) :-
pull_atom( X, ContextName, context_name, maxchars_context_name, UnconsumedChars ).
pull_atom takes some characters to search, the rules for defining what it’s searching for, a maximum number of characters to look at before giving up, and it gives back the found characters alongside the unconsumed characters. Obviously it does a lot of work for us here, but its existence makes the id_context predicate nice and concise to read! This is all something of a humble beginning, but I’m very excited to continue!
In Closing
I hope I’ve piqued your interest in this weird little language. I’ve only scratched the surface of its capabilities here, but I’m sure I’ll be exploring more in the near future. There will be lots to consider going forward if I hope to actually implement my DSL in C# and Prolog, so you can expect some more content about that adventure in the future!
Comments