Prolog
Simon Waite
So I’ve been playing with with Unreal Engine on and off since January, and some folk that know that I’ve been doing a lot of experimenting with games and app-store stuff have said “Why not make a Rogue-Like RPG-Thing?”, and another game-dev friend (who actually has a full-time job in said industry) put my arm up my back and “invited” me to his project. Since I prefer short turn around projects (and his timescale is a couple of years) I thought I’d try and combine the two and try to make a casual-ish RPG and learn UE4 and build some components while I’m at it. I’m a software engineer, right - that’s what I’m supposed to be doing!
So what’s this got to do with Prolog, a language that was very popular before the AI winter? Well it’s all about the skill tree/tech tree/ability trees. It’s a very common element of RPGs, from Planetarion/SkySphere to Skyrim (See below)
UE has a system called Abilities that ought to behave like what you’d expect. However, as it’s new and there’s very little documentation about it, and seems to be under heavy development, with warnings not to use it yet. I tried playing with it, because, well, curiosity. Well, it did kill the cat this time around, or rather the editor crashed, repeatedly. So the hunt for an appropriate tool to fix this … and this was determined to be Prolog. Because these were rules and Prolog’s main use case was building expert systems with lots and lots of rules.
Finding a Prolog to slot into UE4 should be easy right? Just find an open source C++ engine, preferably MIT or PD, make an interface for it to UE4 and the jobs complete. So off we went trying to find sometime suitable. However, the first problem was that there’s a perfectly good open source prolog called SWI Prolog, however, this is a large beast and quite unsuitable for embedding, besides the licence probably would forbid it. Then I remembered a Dr Dobbs article back in the early 90s (back then I read Dr Dobbs as often as I could find the journal in British newsagents). The article covered the use of a public domain prolog by Henri de Feraudy. The articles are here, despite bad formatting. Microsoft Research had an article on the very same here (Archive.org because the original appears lost). As much research as I could, I could not find the original, just one with uncertain providence here. After cleaning it up I put it here on my github. After much looking around, I discovered that it should have been on the Walnut Creek site. Alas, that appears to have died around 2007, breaking a number of mirrors in the process. A friend managed to dig the appropriate CD from archive.org again (all hail archive.org), and I popped the source onto GitHub for posterity - that’s here.
Now that I had a nice toy prolog to play with, I encapsulated it into a C++ class as there were globals everywhere! But it was very well written, and the porting was easy enough. Knowing that I’d probably not have access to stdio files, I encapsulated the file system calls too. Porting this to Unreal was fairly straight forward. However, it became very buggy and crashed a lot. I managed to wrestle it to a level that it didn’t crash the editor, assumptions that malloc’d areas of memory were zero’d etc. But it still had some issues with memory corruption, which resulted in small-prolog aborting safely. Alas, the code involved was quite involved and had a liberal sprinkling of setjmp and gotos, couple this with brain fog due to recent gluten contamination - I found I couldn’t keep the code that I was stepping through all in my head at the same time. I didn’t think it was appropriate putting my non-working results up on github, there’s enough badly working stuff out there as it is without my contributions! :-)
Frustrated by this I set about writing my own, or at least porting one from a simple Java/JavaScript implementation.
So I’m working on that Oct/Nov 2015.
After a few false starts as of early December, I’ve managed to port http://ioctl.org/logic/prolog-latest to C++11. Not completely as yet (no builtins) but it works enough for me to consider it a success for now.
JavaScript, full of lovely lisp-like lambdas and untyped variables, garbage collection and more horrific nonsense that doesn’t track properly to C++ at all.
Garbage collection … most toy C/C++ implementations don’t GC at all.
Which isn’t what you want for a long-running program at all.
Where I’ve not been able to determine object lifecycles I’ve used std::shared_ptr<T> which is a reference counted pointer,
being able to ignore the object lifecycle simplifies programming no end.
Some might say, “Stop that, it’s wrong – you should manually allocate and deallocate your objects”.
“Sure”, I reply – I’ll spend hours writing boilerplate code and still have memory leaks from
where I forgot to write more boilerplate.
I hate boilerplate, we’re programmers – we automate things for a living.
If we can automate something that allows us to safely write complicated code and make our lives easier.
Lambdas … great idea, horrible to debug. Keep them simple, and all will be fine. In C++11 the syntax can seem quite mysterious at times … more practice is needed, but often easier to fall back to function pointers or using java-style interfaces-as-callback classes.
Untyped Variables … luckily, the JS code was simple to figure out what types were used where.
JS Object model … JavaScript allows you to call methods and reference fields which might not exist in objects and throws an exception (or more likely, just stops) if you try to access missing methods on an object passed in by mistake. A horrible franken-class was constructed to represent Terms/Atoms/Rules. Not my best work, but certainly an item on the TODO list.
Strings, Arrays, Maps … because I initially wanted to port this to UE4, and I was working with XCode,
I encapsulated std::string/vector/map into their own classes.
This had an unfortunate side effect of breaking the default implicit copy constructors …
finding things difficult to debug, being time-constrained and not knowing
exactly what was going on under the hood here, I implemented explicit copy methods.
Once I’ve got the built-ins mechanism working, I’ll give porting it over to UE4 a go.
2015/12/28:
Now a decent REPL and a handful of built-ins sorted and stable. Now to see if I can port it to UE4. *gulp*. I’m also wondering if I ought to port it to C# too, so I can use it in unity also. But wait… that’s later … later! :-)
2016/01/01:
New year, new version. Running further tests on the JS port revealed bug after bug. So debug or start again? Brief looking through the code, I wasn’t able to really see what’s going on. So I’m digging out bison and flex and going to write my own. I feel that I’ve learned enough from the port to be able to write my own. (I must quit the habit of throwing away code and starting again … it feels like reinventing the wheel)
2016/01/05:
So any parser needs a grammar to start with: https://github.com/simonkrenger/ch.bfh.bti7064.w2013.PrologParser/blob/master/doc/prolog-bnf-grammar.txt Claims prolog is a bit like this.
<program> ::= <clause list> <query> | <query>
<clause list> ::= <clause> | <clause list> <clause>
<clause> ::= <predicate> . | <predicate> :- <predicate list>.
<predicate list> ::= <predicate> | <predicate list> , <predicate>
<predicate> ::= <atom> | <atom> ( <term list> )
<term list> ::= <term> | <term list> , <term>
<term> ::= <numeral> | <atom> | <variable> | <structure>
<structure> ::= <atom> ( <term list> )
<query> ::= ?- <predicate list>.
<atom> ::= <small atom> | ' <string> '
<small atom> ::= <lowercase letter> | <small atom> <character>
<variable> ::= <uppercase letter> | <variable> <character>
<lowercase letter> ::= a | b | c | ... | x | y | z
<uppercase letter> ::= A | B | C | ... | X | Y | Z | _
<numeral> ::= <digit> | <numeral> <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<character> ::= <lowercase letter> | <uppercase letter> | <digit> | <special>
<special> ::= + | - | * | / | \ | ^ | ~ | : | . | ? | | # | $ | &
<string> ::= <character> | <string> <character>
It misses out lists [ xx , xx , xx ] and the bar notation ( see the wikibooks page for more info)
It also hasn’t got the correct definitions for symbols. But it’s a start.
Lex/Yacc (or these days Flex and Bison) aren’t really great choices for C++ much less a module for a game engine. Luckily, lemon from the SQLite project saves the day. It uses BNF as above too. (Side note: N from BNF died on the 3rd at 87.)
Late last night (or early this morning, depending on how you look at it) I managed to mostly complete the parser with lists and bar notation being incomplete. Next up, tokenising, though I really don’t want to use flex. What to use hand-coded or generated code?
Turns out flex has a experimental C++ option, looked horrid … re2c used instead. There’s a nice tutorial here too.
Looks like I needed makeheaders after all. So now my parser can … parse arbitrary strings I send it. Hurrah!
2016/01/06:
More parsing. More debugging. 50 unit tests so far and growing.
Parsing is almost complete, save for bar notation and queries. I certainly need more unit tests though.
I probably want to sort out strings properly too, but I’ll have to read up on that – I doubt if prolog uses C-style escapes.
Does prolog handle hex and octal numbers? What about backticks? Should I care?
2016/01/07
More parsing changes, graphic chars now are okay to use (eg. # & * + - / < = > ? @ \ ^ ~).
Bar notation is now implemented.
Tracing can be turned on and off as a #define in config.h.
More unit tests! They all pass (though we probably want to do some negative tests)
Should now think about doing an interpreter now :) Nothing more to add today.