Prologomenon Goes Viral

Apparently, social medias like Twitter is all the rage these days. It’s been used to convey critical information in emergency situations, helped revolutions in suppressed governments, and now it’s finally time to overthrow the corrupt imperative languages that have grown fat on the labors of the working class…. Kidding – some of my best friends are imperative languages! I have however started a Twitter account in relation with the blog with the intent to a) troll imperative languages, b) post code-snippets within the character limit that accomplishes something cool. I’ve currently implemented:

All just for fun, of course. Don’t try this at home unless you’re sure you’re able to use cryptic variable/predicate names and abuse all the language features that normally allows one to write readable, concise source code.

An Adventure Game – Part 5

We’re rapidly approaching the end. This time we’ll implement a meta-language that makes it easier to create new games with the existing engine. Conceptually speaking we’re not adding anything new to the table, but the example game from the previous post was created in an ad-hoc manner that demanded knowledge of both Prolog/Logtalk and the engine in question. What we want is a declarative language in which it’s possible to define rooms, entities and how they should be connected. Exactly how this language is interpreted should not be the game designer’s concern. This is a scenario in which it’s best to start with the language itself, since it’s pretty much impossible to write an interpreter otherwise.

The language

We want the language to be capable of:

  • Creating entities.
  • Adding properties to existing entities.
  • Setting new values for entities. For instance, if we first create a door with the default lock we’ll probably want to change this later on.
  • Adding entities to rooms.
  • Connect two rooms with an entrance.

All these steps should be expressible within a single file. The first part might look something like (as always, I’m just making stuff up on the fly, it’s quite possible that there are simpler/better ways to accomplish this!):

begin entities.

build(room, room1, "A rather unremarkable room.\n").
build(room, room2, "...").

build(door, door, "...").

build(lock, lock).

build(key, key, "A slightly bent key.\n").

build(player, player).

end entities.

Where build(Type, Id) should be read as: build an entity of type Type and name it Id. build/3 allows us to create printable entities, where the string is the description. This suggests that we’ll need a builder-object that’s capable of constructing some default entities. Since entities consist of properties, it would be possible to only build generic entities and manually add all the interesting properties in question, but we make the job easier for the game designer if he/she can assume that some primitive objects are already available. Of course, it wouldn’t be practical to demand that all entities are created in this manner. If two entities are identical except for a few differing properties then it would be simpler to create a generic entity and add the properties manually instead of defining a new build-predicate. For example, say that our game will consist of two different kinds of fruits: magical and non-magical. If we eat the former we finish the game, if we eat the latter we increase the health of the player. This is naturally implemented by creating two different properties: fruit\_property and magic\_fruit\_property. Hence, to create two fruits – one magical and one non-magical –  we first create two generic instances and then add the defining properties.

begin entities.

build(generic_entity, apple, "An apple! \n").
build(generic_entity, banana, "A yellow banana. Hot diggity dog!\n").

end entities.

begin properties.

add_property(fruit_property, apple).
add_property(carriable_property, apple).

add_property(magic_fruit_property, banana).
add_property(carriable_property, banana).

end properties.

The Argus-eyed reader will probably realize that it would be ever better to factorize the common properties (carriable\_property) of the two fruits into a prototypical base object, and then clone this object and later add the unique properties (magic\_fruit\_property and fruit\_property).

Since the entities that have been created thus far only has the default values we now turn to the problem of sending messages, so that we’re able to change these at whim. Say that we want to tell the lock that it should use the key that we just created, and the door that it should use the lock. A first attempt might look like this:

begin relations.

action(set_key, lock, key).
action(set_lock, door, lock).

end relations.

All identifiers here refer to the entities that have already been created. This won’t work however, due to a subtle semantic difference between how locks and doors work. A door has a lock, it consists of a lock. Therefore it’s correct to send the lock entity as an argument to set\_lock. A lock on the other hand doesn’t consist of a key. It only needs to know what key will unlock it, hence it’s not correct to send the whole key entity as argument. We only need one part of the key entity, its identity, in this case. To be able to differentiate between these cases we’ll introduce the notation that a term preceded by a dollar sign ($) will be sent as-is, instead of sending the entity corresponding to the identity. The previous attempt should hence be rewritten as:

begin relations.

action(set_key, lock, $ key).
action(set_lock, door, lock).

end relations.

The file will be interpreted from top to bottom, so if we added a property in the preceding block we’re able to change it here. The next step is to connect rooms. Strictly speaking this relation is not necessary since we’re already able to send messages to entities, but including it as a primitive in the language will make it much easier to use. The syntax is:

begin relations.
.
.
.
connect(room1, room2, door).

end relations.

The full example game in all its glory would be written as:

begin entities.

build(room, room1, "A rather unremarkable room.\n").
build(room, room2, "A room almost identical to the previous one. What on earth is going on!?\n").
build(door, door, "A wooden door with a small and rusty lock.\n").
build(lock, lock).
build(key, key, "A slightly bent key.\n").
build(generic_entity, apple, "An apple! \n").
build(generic_entity, banana, "A yellow banana. Hot diggity dog!\n").
build(player, player).

end entities.

begin properties.

add_property(fruit_property, apple).
add_property(carriable_property, apple).

add_property(magic_fruit_property, banana).
add_property(carriable_property, banana).

end properties.

begin relations.

action(set_key, lock, $ key).
action(set_lock, door, lock).

action(set_state, door, $ closed).

action(add_item, room1, apple).
action(add_item, room1, key).

action(add_item, room2, banana).

action(set_location, player, $ room1).

connect(room1, room2, door).

end relations.

A substantial improvement in readability compared to the previous efforts!

Parsing

Another boring, dry entry on parsing? Fear not, because I have a trick up my sleeve -there was a reason why the syntax of the meta-language was a spitting image of Prolog’s all along! One way to interpret the file is to say that begin/end and the dollar sign are all operators with a single argument. Then the file is nothing but a collection of facts that can be accessed as normal and we won’t have to worry about parsing at all. A slightly more contrived but more general approach is to use what in Prolog-nomenclature is known as term expansion. This is usually the preferred approach to handle embedded languages and is somewhat similar to macros in Lisp. The basic idea is simple: instead of taking a term at face-value we expand it according to a user-defined rule. What’s the point? Basically we don’t have to type as much. For example, let’s say that we have a database consisting of rule/3 facts, where the first argument is an atom, the second a list and the third an integer denoting the length of the list.


rule(a, [], 0).

rule(b, [a], 1).

Furthermore assume that we don’t want to calculate the length of the second argument at run-time. There’s nothing inherently wrong with this approach, but manually entering the length of the list is a drag and quite error-prone. It would be better if we could simply write:


rule(a, []).

rule(b, [a]).

And tell the Prolog system that these facts should be construed as rule/3 facts with an additional third argument which contains the length of the list. Fortunately this can easily be realized with the built-in predicate term\_expansion/2. The first argument of term\_expansion is the term that shall be expanded. The second argument is the expanded term. A suitable definition for the previous example is:

term_expansion((rule(Head, Body)), rule(Head, Body, Length)) :-
    length(Body, Length).

Great success! We don’t have to concern ourselves with how or when this predicate is called, just that it will eventually be called when the file is loaded. Like all powerful language constructs it’s easy to abuse the term expansion mechanism and create unreadable code. We could for instance expand A :- B to B :- A if we were in a facetious mood (don’t do it, OK?). Fortunately the Logtalk support is a bit more sane than in most Prolog systems. Instead of defining term\_expansion/2 rules in the same file as the rules that shall be expanded, they’re encapsulated in a special expansion object. This object is later used as a hook in logtalk\_load/2 to make sure that the effect is localized to a given file. In summary, there’s two steps involved:

  • Define the term\_expansion/2 rules in an expansion object (which must implement the expanding protocol).
  • Load the file (the script file in our case) with the expansion object.

I shan’t spell out the full details of the expansion object, but what it does is to remove the begin/end directives and create a set of entity/1 facts with the initial entities. Also, to make things easier in the script interpreter, it removes add\_property/2, action/3, connect/3 and replaces them with unary facts instead.

The builder

The builder is in charge of building game entities. As mentioned earlier it’s not strictly needed since it’s always possible to add properties manually, but it does simplify things. Here’s how a map and a room could be created:

    build(world, Id, Rooms, Player, World) :-
        Ps = [map_property-State],
        build(final_state, F),
        map_property::new([[F|Rooms], Player], State),
        entity::new(Ps, Id, World).

    build(room, Id, Description, Room) :-
        Ps = [container_property - State1,
              printable_property - State2],
        container_property::new([], State1),
        printable_property::new([Description], State2),
        entity::new(Ps, Id, Room).

Interpreting

We have a description of the game and want to transform it into an entity that has the map\_property. Strictly speaking this is not an interpreter, but rather a compiler from the script language to the entity language. The most important predicate is interpret\_game/2 that takes an expanded script file as argument and produces a game world. It works by extracting the entity directives, the property directives, the relations directives and then separately interprets each one of these. Finally it extracts the rooms and the player and asks the builder to build a game world.

   interpret_game(DB, World) :-
       findall(E, DB::entity(E), Es0),
       findall(P, DB::add_property(P), Ps),
       findall(A, DB::action(A), As),
       findall(C, DB::connect(C), Cs),
       interpret_properties(Ps, Es0, Es1),
       interpret_actions(As, Es1, Es2),
       interpret_connectors(Cs, Es2, Es),
       get_rooms(Es, Rooms),
       get_player(Es, Player),
       builder::build(world, world1, Rooms, Player, World).

The interpret\_x predicates are all rather similar. They iterate through the list of commands and changes the set of entities accordingly. For brevity, let’s concentrate on interpret\_actions/3.

    interpret_actions([], Es, Es).
    interpret_actions([t(M, Id1, Id2)|As], Es0, Es) :-
        select_entity(Id1, Es0, E0, Es1),
        lookup_argument(Id2, Es0, Arg),
        entity::action(M, [Arg], E0, E),
        interpret_actions(As, [E|Es1], Es).

    lookup_argument(Id, Es, Arg) :-
        (   Id = $(Symbol) ->
            Arg = Symbol
        ;   lookup_entity(Id, Es, Arg)
        ).

The body of interpret\_actions/3 should be read as: execute action M on the entity corresponding to Id1 with the argument Id2 (remember that arguments preceded by a dollar-mark are left unchanged). Since we might need to update an entity several times, it’s re-added to the list of entities whenever it’s updated.

Putting everything together

We need to make a small change to init/0 in the game object. Instead of building a world manually it’ll take a script file as argument and ask the interpreter to interpret (compile!) it.

    init(Game) :-
         write('Welcome to Bacchus-Bosch!'), nl,
         current_input(S),
         script_interpreter::interpret_game(Game, World),
         repl(S, [], World).

That’s pretty much it – the end of Bacchus-Bosch. As I suspected when I started the project the final game isn’t very fun. Wait, scratch that, it might be the worst game I’ve ever played, and that includes the infamous yellow car game. But it does have a magic banana, that ought to count for something. In any case it wouldn’t be hard to create more engrossing games since all the building blocks are in place. It should also be noted that the engine is hardly limited to text-based or turn-based games. In a real-time game we could for instance run the update method a fixed amount of times per second instead of waiting for player input. We could also add e.g. role playing elements by defining new properties.

I hope that this pentalogy has been at least somewhat comprehensible and coherent. What the future holds for the blog I dare not promise. Hopefully we’ll someday see the return of the magic banana!

Source code

The source code is available at https://gist.github.com/924052.

An Adventure Game – Part 4

And yet again I display exceptional prowess in the (un)holy art of procrastination. This time I blame lack of coffee, Sweden’s gloomy weather and the Illuminati. This post will concern two of the three remaining obstacles. First we’re going to add enough properties so that we can create a map consisting of a few rooms together with some entities. Second, we’re going to translate the parsed commands from the user into a suitable set of action commands and execute them with respect to the game world and its entities. As always it’s best to start with a use-case scenario and extrapolate some requirements.

> look

You see a small, rusty key and a door.

> pick up the key and open the door.

> go through the door.

This room is almost identical to the previous one. How eerie. You see a banana and a door.

> eat the door.

no.

> eat the banana

no.

> take the banana and eat it.

Congratulations! You solved mystery of the missing banana!

Let’s don our declarative thinking cap. This particular game consists of two rooms and a player. The player starts in the first room, picks up the key, unlocks the door and enters the second room where he/she in a moment of absolute intellectual clarity manages to deduce that the only way to beat the game is to eat the banana. Just like in real life. We can summarize the requirements as:

  • The player must be able to move from one location to another.
  • The player must be able to reference entities by their names.
  • The door must be linked to the second room.
  • The key must be able to lock/unlock the door.
  • The banana must have the property that the game stops when the player eats it.

Fortunately we can already handle some of these. The most fundamental requirement is that of referencing entities. Since each entity is just a list of properties we’re currently unable to distinguish them in any sensible way. The most obvious solution is to add another property, identity\_property, which describes the property of having an identity. For example, the door in the scenario would be represented by the list:

[openable\_property-State_1, printable\_property-State_2, ..., identity\_property-State_n]

For simplicity the state of identity\_property is just going to be an atom, e.g. door. In a real implementation it would of course be preferable to use a more complex data structure so that entities can be referenced by attributes as well, e.g. “wooden door”, but the basic idea is the same. Of course, just because this is a nice, declarative solution doesn’t mean that it’s good. To quote Richard O’Keefe from The Craft of Prolog:

The nasty thing about declarative programming is that some clear specifications make incredibly bad programs.

It’s not to hard to see that storing the identity of an entity as a property is hopelessly inefficient. To find an entity in a container we have to iterate through the whole container and check whether or not every element satisfies the identity property in question. Ouch. It would be a much better idea to demand that all entities have an identity and then store the container as a tree where nodes are entities ordered by their identities. Of course, it doesn’t mean that I’m going to use this solution just because it’s better! Sometimes it’s enough to be aware that something is a potential bottleneck and fix it if/when it becomes a real problem. Or buy a faster computer.

Next up is the problem of the game world. We shall introduce a new property by the name map\_property and stipulate that it consists of a list of rooms and a player. Why not add the player as an item in the current room instead? Just for simplicity; it’s slightly easier to move the player from room to room if we don’t have to explicitly remove him/her from the first room and add him/her to the new one. Since we have removed the player from the rooms we’re going to need another property, that of having a position/being movable, so that it’s always possible to find the current room.

:- object(movable_property,
    extends(property)).

    new(identity_property-_).

    action(move, [New], Owner, _, Owner, New).

    action(get_location, [Room], Owner, Room, Owner, Room).
:- end_object.

The state of movable\_property is simply an identity property. When someone issues the move command the current location is changed. Exactly how this works should become clearer later on. For now, let’s concentrate on implementing map\_property. Its state will be a tuple of a list of rooms and the player, and it’ll have commands to add/remove rooms, get the current room, update the rooms and so on.

:- object(map_property,
    extends(property)).

    new([]-[]).

    update(E0, E) :-
        entity::update_property(map_property, E0, Rooms0-P0, Rooms-P, E),
        entity::update(P0, P),
        update_rooms(Rooms0, Rooms).

    update_rooms([], []).
    update_rooms([R0|R0s], [R|Rs]) :-
        entity::update(R0, R),
        update_rooms(R0s, Rs).

    action(add_rooms, [Rooms1], Owner, Rooms2-P, Owner, Rooms-P) :-
        ...

    action(get_room, [Property, R], Owner, Rooms-P, Owner, Rooms-P) :-
        ...

    action(select_room, [Property, R], Owner, Rooms-P, Owner, Rooms1-P) :-
        ...

    action(print, [], Owner, Rooms-P, Owner, Rooms-P) :-
        action(current_room, [Room], Owner, Rooms-P, _, _),
        entity::action(print, [], Room, _).

    action(current_room, [Current], Owner, Rooms-P, Owner, Rooms-P) :-
        entity::action(get_location, [Id], P, _),
        list::member(Current, Rooms),
        entity::get_property(Current, Id).

    action(get_player, [P], Owner, Rooms-P, Owner, Rooms-P).

:- end_object.

It’s not necessary to study the details of this particular implementation, but some of the predicates demand an explanation. update/2 uses update\_property/5 in entity to update map\_property with the state obtained by updating the list of rooms and the player. To put it more simply: it just calls update/2 on the rooms and the player. The print command extracts the current room and prints it (it would not be very interesting to print anything else). The current\_room command gets the current location of the player and then uses member/2 to find the room with that particular identity.

Then there are doors. To have a text-game without lots of doors would simply be madness. Given the representation of the game world, each door must contain the identity of the area which it leads to. It just stores the identity, not the area itself (since all areas are stored in the map\_property). We shall store this identity in entrance\_property:

:- object(entrance_property,
    extends(property)).

    new(identity_property-_).

    action(get_location, [Location], Owner, Location, Owner, Location).
:- end_object.

So when we create a door we plug in an entrance\_property with a suitable identity of a room.

Translating commands to entity actions

Before we begin the translation process we’re going to define some useful action commands in container\_property and map\_property. The most frequently used action will be that of extracting  an entity according to some property (e.g. the identity), perform some state-changing operation and then adding it anew. This procedure is necessary since we don’t have explicit state: whenever we extract an entity we get a copy of it, and changes to this copy won’t affect the original. For this purpose we’re going to define two additional action commands in container\_property and map\_property that takes three arguments:

  • P – the property of the entity that shall be updated.
  • Old – will be unified with the old entity.
  • New – the new entity.
:- object(container_property,
    extends(property)).

     .
     .
     . % As before.

    action(update_item, [P, Old, New], Owner, Items, Owner, [New|Items1]) :-
        list::select(Old, Items, Items1),
        entity::get_property(Old, P).

    .
    .
    . % As before.
:- end_object.

The neat thing about this definition is that we can extract an entity with Old and simply pass a variable as New, and unify this variable to the updated entity later on. The definition in map\_property is similar, but works for the player and the current room.

:- object(map_property,
    extends(property)).

    .
    .
    . % As before.

    action(update_current_room, [Current0, Current],
           Owner, Rooms-P, Owner, [Current|Rooms1]-P) :-
        entity::action(get_location, [Id], P, _),
        list::select(Current0, Rooms, Rooms1),
        entity::get_property(Current0, Id).

    action(update_player, [P0, P], Owner, Rooms-P0, Owner, Rooms-P).

    .
    .
    . % As before.

:- end_object.

Now we can finally begin with the translation process. Since we know that the input from the user will be a list of commands (remember that conjunctions are allowed) we will execute them one by one and thread the state of the game world.

eval_commands([], World, World).
eval_commands([C|Cs], World0, World) :-
    write('The command is: '), write(C), nl,
    eval_command(C, World0, World1),
    eval_commands(Cs, World1, World).

Each eval\_command/3 rule changes the state of World0 to World1 according to the command in question. The simplest one is the look-command with no arguments, that just prints the current room:

    eval_command(look-[], World, World) :-
        entity::action(current_room, [Room], World, _),
        write('You see: '), nl,
        entity::action(print_children, [], Room, _).

It asks the game world for its current room and then issues the print\_children command. The take-command is slightly more convoluted. It takes an identity as argument, tries to find the entity in question and asks the player to pick it up.

eval_command(take-[Id], World0, World) :-
    entity::action(update_current_room, [R0, R], World0, World1),
    entity::action(update_player, [P0, P], World1, World),
    entity::action(select_item, [identity_property-Id, Item], R0, R),
    entity::action(add_item, [Item], P0, P).

The move-command is perhaps the most complex of the bunch, but follows the same basic structure:

    eval_command(move-[Id], World0, World) :-
        entity::action(current_room, [Room], World0, _),
        entity::action(update_player, [P0, P], World0, World),
        entity::action(get_item, [identity_property-Id, Entrance],
                       Room, _),
        entity::action(open, [], Entrance, _),
        entity::action(get_location, [Location], Entrance, _),
        entity::action(move, [Location], P0, P).

It tries to find and open the entrance in the current room, asks it where it leads and finally asks the player to move to that location. The lock/unlock and open/close commands are implemented in the same way. One problem remains though: it’s possible to take the key, unlock the door, open it and go through it, but no way to actually finish the game. Just like everything else this functionality can be implemented in a number of ways. It might be tempting to somehow augment the top-loop and in every iteration check whether or not the final state have been reached, but this is needlessly complicated. Instead we’re going to introduce a special entity with only two properties, that of having the identity final\_state and that of being printable. It’s constructed as:

    build_win_screen(Screen) :-
        Screen = [printable_property - State, identity_property-final_state],
        State = "Congratulations! A winner is you!\n (No, you can't quit. Stop trying.)\n".

Then we need an object that has the effect that it asks the player to move itself to the final state whenever it is used, for instance a banana.

:- object(fruit_property,
    extends(property)).

    action(dissolve, [E0, E], Owner, State, Owner, State) :-
        entity::action(move, [identity_property-final_state], E0, E).

:- end_object.

The banana entity is created by combining an identity, a printable, a carriable and a fruit property:

    build_test_banana(Banana) :-
        Banana = [fruit_property - State1, printable_property-State2,
                  identity_property-banana, carriable_property-State3],
        fruit_property::new(State1),
        banana_description(State2),
        carriable_property::new(State3).

Then we of course need an eat-command, but this is straightforward to implement. So what happens when the player eats the banana is that the current location changes to final\_state. This room doesn’t have any entities and doesn’t support any operations besides being printed, which means that the player can’t return to the rest of the game world and have completed the game.

Putting everything together

We shall use the top-loop from part 2, but with some modifications. The input will be parsed into commands that are executed with respect to the current game world. The loop then calls itself recursively with the new state and asks for new input.

    init :-
         write('Welcome to Bacchus-Bosch!'), nl,
         current_input(S),
         build_test_world(World),
         repl(S, [], World).

    repl(S, History, World0) :-
        entity::update(World0, World1),
        entity::action(print, [], World1, _),
        write('> '),
        nlp::parse_line(S, Atoms),
        write('The input is: '),
        meta::map([X] >> (write(X), write(' ')), Atoms), nl,
        nlp::tag_atoms(Atoms, AtomTags),
        write('The tagged input is: '),
        meta::map([X] >> (write(X), write(' ')), AtomTags), nl,
        (   eval(History, AtomTags, World1, World) ->
            true
        ;   write('no.'), % This is Prolog after all.
            nl,
            World = World1
        ),
        write('-------------------'), nl,
        repl(S, AtomTags, World).

    eval(History, AtomTags, World, World1) :-
        nlp::resolve_pronouns(History, AtomTags, AtomTags1),
        nlp::parse_atoms(AtomTags1, _, Commands),
        eval_commands(Commands, World, World1).

Like a professional TV-chef I prepared a small test world and got the following result (with some of the debug output omitted):

Welcome to Bacchus-Bosch!
A rather unremarkable room.
> look

You see:
A slightly bent key.
A wooden door with a small and rusty lock.
——————-
A rather unremarkable room.
> open the door

no.
——————-
A rather unremarkable room.
> take the key and unlock the door with it

——————-
A rather unremarkable room.
> go through the door
——————-
A room almost identical to the previous one. What on earth is going on!?
> look

You see:
A yellow banana. Hot diggity dog!
A wooden door with a small and rusty lock.
——————-
A room almost identical to the previous one. What on earth is going on!?
> take the banana
——————-
A room almost identical to the previous one. What on earth is going on!?
> eat it
——————-
Congratulations! A winner is you!
(No, you can’t quit. Stop trying.)

The final herculean task, the creation of a script-language, is saved for the next entry!

Source code

The source code is available at https://gist.github.com/900462.

An Adventure Game – Part 3

I’ve been procrastinating too much. It’s time to roll up our sleeves and get dirty with the nitty-gritty core of Bacchus-Bosch. We’re currently able to read input from the player and parse commands. Before even considering how commands should be executed we have to take a step back and make some ontological commitments. We know that the game will consists of interaction between game objects, the entities, but haven’t specified how these should be represented or how they are created. It might be tempting to simply use a set of unit clauses and statically recite everything of interest:

entity(key).
entity(room_1).
entity(room_2).
entity(door).

contains(room_1, key).
contains(room_1, door).

connected(room_1, door, room_2).
.
.
.
%And so on for the whole level.

At a first glance this might look like an acceptable solution. It wouldn’t be very hard to add e.g. properties to the entities by adding more facts, but everything breaks down in the moment when the player changes the state of the world by picking up the key. Then the key is no longer directly contained by the room and should instead be added to the inventory of the player. The quick and easy hack is to use assert/retract in order to add and remove facts according to the fluctuating state of the game world, but in the long run that’s a terrible idea. To be forced to use impure features for such an integral part of the game is either a sign that we’re using the wrong data structures or the wrong language. I’ll go with the former theory!

Let’s begin by considering a simplified problem where the game only consists of a player with the property of having health in the form of an integer: “hit points”. It should be possible to both increase and decrease this value according to events from other entities. What’s an entity? A common and simple solution is to create a class hierarchy with an abstract class in the top and concrete classes such as items and monsters in the lower layers. While there’s nothing inherently wrong with this I think we can do better, for two reasons:

  • The class hierarchy will be huge and hard to make sense of.
  • It’s not (at least not in most languages, Logtalk happens to be an exception) possible to create new classes during runtime, with the effect that behaviour can’t be modified or extended once the game has started.

An often cited design principle is to favor composition over inheritance. We want the entities to be entirely composed of smaller objects, of properties. The sum of all the properties constitute the entity – nothing more, nothing less (followers of holism should stop reading here!). It should of course be possible to both add, remove and update properties during runtime. It’s easiest to start with a basic definition of a property, which we’ll do with a prototypical object. A property should be able to:

  • Give the initial state of the property. For the health property, this might simply be a positive integer.
  • Update the entity to which the property belong. If the property doesn’t directly influence the entity, it’s left unchanged.
  • Execute an action that changes the state of the property, e.g. increasing or decreasing the health.

With these considerations the object becomes:

:- object(property).
    :- info([
        version is 1.0,
        author is 'Victor Lagerkvist',
        date is 2011/03/19,
        comment is 'A property constitutes the basic behaviours of the objects in Bacchus-Bosch.']).

    :- public(update/2).
    :- mode(update(+entity, -entity), zero_or_more).
    :- info(update/2, [
        comment is 'Update the entity to which the property belong.',
        argnames is ['Entity', 'Entity1']]).

   :- public(action/6).
    :- mode(action(+atom, +list, +entity, +state, -state, -entity), zero_or_more).
    :- info(action/6, [
        comment is 'Execute the action Name with respects to Args, State and Entity, and store the resulting new state and entity in State1 and Entity1.',
        argnames is ['Name', 'Args', 'Entity', 'State', 'Entity1', 'State1']]).

    :- public(new/1).
    :- mode(new(-term), zero_or_more).
    :- info(new/1, [
        comment is 'Unify State with the initial state of the property.',
        argnames is ['State']]).

    %% Basic definition: do nothing!
    update(E, E).

    %% Basic definition, overloaded in almost every descendant prototype.
    new(void).

:- end_object.

Exactly how these predicates should be implemented will be clearer with an example.

:- object(health_property,
    extends(property)).

    new(10).

    action(decrease_health, [], Owner, H0, Owner, H) :-
        H is H0 - 1.
    action(increase_health, [], Owner, H0, Owner, H) :-
        H is H0 + 1.

:- end_object.

Hence, the initial state for the health property is 10. To decrease the value one calls action/6 with the correct action name, an empty argument list, the owner of the property and the old state, and in return obtains the updated owner and new state with the fifth and sixth parameters. If a property doesn’t support a specific action it’ll simply fail. Let’s see how update/2 can be used together with the health property. It should be called in each tick of the game. For example: the health should be decreased if the player is poisoned or have somehow been ignited. Such a property won’t support any actions and only overload the definition of update/2 from property.

:- object(on_fire_property,
    extends(property)).

    update(E0, E) :-
        entity::action(decrease_health, [], E0, E).

:- end_object.

Since update/2 takes an entity as argument, the on_fire property simply asks this entity to decrease its health. Now we have to decide how to represent entities and how to delegate action messages. As mentioned earlier an entity is simply the sum of its properties, hence we can simply represent it as a list that contains properties and their states. The formal definition reads:

  • [] is an entity.
  • [P|Ps] is an entity if Ps is an entity and P is a tuple of the form: N - S, where N is the name of a property and S is a state of that property.

Continuing on our example, [health\_property - 10] is an entity. If we decide to have some fun and for a moment indulge ourselves with arson, [health\_property - 10, on\_fire\_property - void] is also an entity. A few basic definitions remain before we can actually do anything with these entities. First we need a predicate update/2 that iterates through the list of properties that constitute the entity and calls update/2 for every property.

update(E0, E) :-
    update(E0, E0, E).

update(E, [], E).
update(E0, [P|Ps], E) :-
    P = Name - _,
    Name::update(E0, E1),
    update(E1, Ps, E).

The effect is that each property is updated with respect to the current state of the entity. Next up is action/4. It takes the name of the action that shall be performed, its arguments, the entity in question and returns the updated entity if the action could be performed or simply fails otherwise. Since an entity can’t perform any actions it has no choice but to try to delegate the action to its properties.

action(A, Args, E0, E) :-
    %% Select a property from the list such that the action A can
    %% be performed with the arguments Args.
    list::select(P, E0, E1),
    P = PropertyName - State,
    PropertyName::action(A, Args, E1, State, E2, State1),
    %% Add the property with the updated state to E2.
    P1 = PropertyName - State1,
    E = [P1|E2].

As seen from the code action/4 uses select/3 to find the first property that supports the operation. If there’s more than one potential property it will simply choose the first one but leave choice point for the others. If we put it together into one massive object we get:

:- object(entity).

    :- info([
        version is 1.0,
        author is 'Victor Lagerkvist',
        date is 2011/03/20,
        comment is 'The entity operations of Bacchus-Bosch.']).

    :- public(update/2).
    :- public(action/4).
    :- public(get_property/2).
    :- public(select_property/3).

    update(E0, E) :-
        %% As before.

    action(A, Args, E0, E) :-
        %% As before.

    get_property(E, P) :-
        list::member(P, E).

    select_property(P, E, E1) :-
        list::select(P, E, E1).

This is more or less the basic building blocks, the engine, but of course quite a lot of work remains before we have an actual game in our hands. For the remainder of the post we shall implement enough properties so that it’s possible to construct a room with some entities in it. A room is an entity that contains other entities. We can model this as a property, namely the property of being a container. This property at least has to support the following operations:

  • Being able to update the state of its children, i.e. overload update/2 from its parent.
  • Add and remove items with actions.

For simplicity the data structure is going to be a list of entities. This makes it almost trivial to write the actions.

:- object(container_property,
    extends(property)).

    new([]).

    update(E0, E) :-
        entity::select_property(container_property-Items, E0, E1),
        update_children(Items, Items1),
        E = [container_property-Items1|E1].

    update_children([], []).
    update_children([E|Es], [E1|E1s]) :-
        entity::update(E, E1),
        update_children(Es, E1s).

    action(add_item, [E], Owner, Items, Owner, [E|Items]).

    action(remove_item, [E], Owner, Items, Owner, Items1) :-
        list::select(E, Items, Items1).
:- end_object.

Then we of course need a door. Doors are awesome: you can walk through them, open them, close them, lock them – the only limit is the imagination! Our particular door will only have one property though, that of being openable. But it’s only possible to open a door if it happens to be unlocked, hence the openable property in turn depends on whether or not the lock can be unlocked with the key in question. For simplicity we’re going to assume that the player uses the key every time he/she wishes to open the door, but extending these properties so that the lock has an internal state would not be terribly difficult.

:- object(openable_property,
    extends(property)).

    new(closed-[lock_property- Lock]) :-
        lock_property::new(Lock).

    action(open, Key, Owner, closed-Lock, Owner, open-Lock) :-
        entity::action(unlock, Key, Lock, _).
    action(close, [], Owner, _-Lock, Owner, closed-Lock).

:- end_object.

The action/6 command should be read as: change the state of the door from closed to open if the key can unlock the lock. To complete the door we of course need to define the lock and key properties.

 :- object(key_property,
    extends(property)).

    %% The default key.
    new(key).

:- end_object.

:- object(lock_property,
    extends(property)).

    %% The (default) key that opens the lock.
    new(key).

    valid_key(E, Key) :-
        entity::get_property(E, key_property-Key).

    action(lock, [Entity], Owner, Key, Owner, Key) :-
        valid_key(Entity, Key).
    action(unlock, [Entity], Owner, Key, Owner, Key) :-
        valid_key(Entity, Key).

:- end_object.

The two actions specifies that the entity can lock or unlock the lock if it has the property of being a key with the correct state. Note that the entity in question doesn’t just have to be a key, it can still support other properties as long as the key property is fulfilled.

We’re now able to create a room with a door and a key. What remains is the player. For the moment that’s just an entity that has the property of having health, which we defined earlier, and that of having an inventory. The Argus-eyed reader will probably realize that having an inventory is quite similar to that of being a container. The only difference is that the player can only pick up items that are carriable, so instead of defining everything from the ground up we’re going to inherit some definitions from container\_property. What happened to the principle of favoring composition over inheritance? Bah!

:- object(inventory_property,
    extends(container_property)).

    valid_item(E) :-
        entity::get_property(E, carriable_property-_).

    action(add_item, [E], Owner, Items, Owner, [E|Items]) :-
        valid_item(E).

    action(drop_item, [E], Owner, Items, Owner, Items1) :-
        valid_item(E), % This shouldn't be necessary since only valid item are added in the first place.
        list::select(E, Items, Items1).

:- end_object.

:- object(carriable_property,
    extends(property)).

    %% Perhaps not the most interesting property in the game.

:- end_object.

It should be noted that I haven’t actually tested most of these properties, but it should/could work! So do we now have a functional but simplistic game? Not really. We have the basic entities, but there’s a quite glaring omission: everything is invisible since nothing can be printed. For a text game this is a distinct disadvantage! The simplest solution is to add another property, that of being printable, where the state is the string that shall be displayed.

:- object(printable_property,
    extends(property)).

    new(Description) :-
        list::valid(Description).

    action(print, [], Owner, Description, Owner, Description) :-
        format(Description).
:- end_object.

But since we also want the possibility to print items in a container, e.g. a room, we’re going to define an additional action in container\_property.

:- object(container_property,
    extends(property)).

    new([]).
    .
    . % As before.
    .

    action(print_children, Args, Owner, Items, Owner, Items) :-
        % Print all children that are printable.
        meta::include([E] >>
                       (entity::action(print, Args, E, _)),
                      Items,
                      _).
:- end_object.

Putting everything together

Let’s use the properties and construct some entities. The test program is going to build a room and then print its description together with its children.

    init :-
        write('Welcome to Bacchus-Bosch!'), nl,
        build_test_room(Room),
        entity::action(print, [], Room, Room1),
        write('You see: '), nl,
        entity::action(print_children, [], Room1, _Room).

Building the room and its components is not hard, just a bit tedious.

    build_test_room(Room) :-
        build_test_door(Door),
        build_test_player(Player),
        build_test_key(Key),
        Room0 = [container_property - State1, printable_property - State2],
        container_property::new(State1),
        room_description(State2),
        entity::action(add_item, [Door], Room0, Room1),
        entity::action(add_item, [Player], Room1, Room2),
        entity::action(add_item, [Key], Room2, Room).
    build_test_door(Door) :-
        Door = [openable_property-State1, printable_property-State2],
        openable_property::new(State1),
        door_description(State2).

    build_test_key(Key) :-
         Key = [key_property-State1, printable_property-State2],
         key_property::new(State1),
         key_description(State2).

    build_test_player(Player) :-
        Player = [inventory_property-State1, health_property-State2],
        inventory_property::new(State1),
        health_property::new(State2).

The string descriptions are simply given as facts.

    room_description("A rather unremarkable room.\n").
    door_description("A wooden door with a small and rusty lock.\n").
    key_description("A slightly bent key.\n").

When running the test program we get the following output:

Welcome to Bacchus-Bosch!
A rather unremarkable room.
You see:
A slightly bent key.
A wooden door with a small and rusty lock.
true

Only three major obstacles remain before we have a game in our hands:

  • More properties.
  • Conjoin the parsed commands with the game world so that it’s possible for the user to interact with entities. It shouldn’t be too hard to see that commands will be executed by sending action commands to the entities in question.
  • Abstract the creation of game objects, e.g. with the help of an embedded language.

Which will be the topics of the next post. Stay tuned!

Source code

The source code is available at https://gist.github.com/878277.

An Adventure Game – Part 2

When we left off last time we were able to read input from the player and tag the atoms with their word classes. This time we’ll use this information to analyze what the input means with two different techniques: pronominal anaphora resolution and chunk-based parsing. Don’t worry about the technical names – I’m way to lazy to do something that would actually be strenuous, so the presented solutions won’t be that hard to grasp. Let’s have a look at some typical user input and some potential answers:

> look

You are in a dimly lit room. A banana hangs from the ceiling in a thin, plastic wire.

> look at the banana

It’s a typical banana. Yellow, crooked and utterly delicious. Mmm.

> eat it

The banana is out of reach.

> grab the banana and eat it

Not even your long, hairy ape-arms are enough to bridge the vast gap.

> fling feces around the room

I’m sorry. I don’t know what ‘fling’ means.

All these sentences have something in common: they are imperative in nature and somehow either changes the state of the game world or inspects it. We’ll make the basic assumption that every command can be described as a tuple, C-Args, where C is an atom and Args is a list of tags. The “look”-command from the example can be represented as:

command(look, [entity]).
command(look, []).

Since a banana is an entity, the sentence “look at the banana” can be parsed as a look-command with “banana” as argument. It can also be parsed simply as “look”, with no argument at all, but the first interpretation is preferable. There is however one problem that we must tackle before the parsing can take place: what does “it” mean? That depends on the context and is the subject of pronominal resolution.

Pronominal resolution

Just like everything else in natural language processing, resolving pronouns is quite challenging in the general case. Fortunately we’re dealing with a rather restricted subset of English. When a pronoun such as “it” is used we can make the assumption that it’s just a shorthand for a previously identified entity. The task then becomes to replace all occurrences of a pronoun with the corresponding entity before the parsing. Let’s have a look at a few examples:

> take the banana and eat it

Here the pronoun refers to the banana, i.e. the sentence should be replaced by “take the banana and eat the banana”.

> look at the ceiling and take the banana and eat it

Here the pronoun probably refers to the banana, but it could possibly also refer to the first entity: the ceiling. Since we always want the possibility to backtrack and try alternative solutions in case the first one fails later on, it’s a good idea to make the predicate non-deterministic. Assuming that we’re given a list of tagged atoms, a simple algorithm may look as follows:

  • If the list of tagged atoms is non-empty, inspect the first element.
  • If it’s not a pronoun, ignore it and continue with the rest of the list.
  • If it’s a pronoun, replace the pronoun with the corresponding entity, where the candidates of possible entities are the tagged atoms that occur to the left of the pronoun in the sentence.

Putting this into code is straightforward. The predicate will have three arguments: the list of tagged atoms, the tagged atoms that have been processed so far and the result.

    resolve_pronouns(ATs, Xs) :-
        resolve_pronouns(ATs, [], Xs).

    resolve_pronouns([], _, []).
    resolve_pronouns([A-T|Xs], Pre, [Y|Ys]) :-
        (   T = pronoun ->
            resolve_pronoun(A, Pre, Y),
            resolve_pronouns(Xs, Pre, Ys)
        ;   Y = A-T,
            resolve_pronouns(Xs, [Y|Pre], Ys)
        ).

resolve\_pronoun/2 is also a walk in the park. For now, we’re only going to be dealing with “it”. Other pronouns can be added in a similar manner.

    %% NAME:
    %%  resolve_pronoun(Pronoun, AtomTags, X)
    %% DESCRIPTION:
    %% True if X is an entity corresponding to the pronoun resolved
    %% with the help of AtomTags. It is the caller's responsibility to
    %% make sure that AtomTags is in the correct (possibly reversed)
    %% order.
    resolve_pronoun(it, Xs, X) :-
        X = A-entity,
        list::member(X, Xs).

Nota bene: since the words are pushed onto Pre in LIFO order, a pronoun will be resolved from right-to-left. While this algorithm is indeed very simple, it’s not particularly efficient. Due to the call to member/2 in resolve\_pronoun/2, the worst case execution time (to find one solution) for resolve\_pronouns/2 is exponential. But considering the fact that a typical sentence is just a few words long and that they rarely if ever contains more than one or two pronouns, I think we’ll survive.

One step remains. Note that “it” is used in one of the example sentences without referring to anything in that particular sentence. Instead it refers to the entity that was used in the previous sentence. The obvious yet quite flexible solution is to augment resolve\_pronouns/2 with an additional argument that holds the previous sentence. Then a pronoun can first be resolved with respect to the current sentence, but if that fails the previous sentence is tried instead.

Parsing

Natural language contains a lot of noise and variations. This makes formal methods such as context-free grammars somewhat ill-suited and cumbersome to use. One deceivingly simple solution is to ignore everything that we’re not interested in and group the good stuff into chunks. A command, e.g. “eat”, can be considered a chunk. We know that it takes one entity-argument, so after encountering the command chunk we scan the rest of the sentence for an argument chunk of the correct type. This might sound like cheating – and it kind of is – but as long as the reduced, simpler problem still yields the correct output that’s hardly of any importance.

The goal is to produce one or more commands given a list of tagged atoms (where the pronouns are resolved). Remember that commands are defined as:

        command(look, [entity]).
        command(look, []).
        command(eat, [entity]).

To allow some flexibility in the input, we’re also going to allow synonyms. These can be defined as additional facts.

    variants(look ,[look, inspect]).
    variants(eat, [eat, munch, digest]).

For every chunk of type X we’re going to write a corresponding X\_chunk predicate that has 3 arguments: the list of tagged atoms, the list that remains after this chunk is parsed, and the resulting chunk. First off is the sentence chunk.

    %% NAME:
    %%  parse_atoms(+AtomTags, -Remainder, -Commands)
    %% DESCRIPTION:
    %% True if Commands is a list of commands parsed from from the atoms and their
    %% tags in AtomTags.
    parse_atoms(ATs, Remainder, Commands) :-
        sentence_chunk(ATs, Remainder, Commands).

    %% NAME:
    %%  sentence_chunk(+AtomTags, -Remainder, -Commands)
    %% DESCRIPTION:
    %% True if Commands is a list of commands parsed from from the atoms and their
    %% tags in AtomTags. The remainder, i.e. the chunk after the
    %% sentence, is stored in Remainder (most likely just the empty list).
    sentence_chunk(ATs, Remainder, [C-Args|Cs]) :-
        command_chunk(ATs, ATs1, C),
        argument_chunk(ATs1, C, ATs2, Args),
        (   conjunction_chunk(ATs2, Remainder0, _) ->
            sentence_chunk(Remainder0, Remainder, Cs)
        ;   Cs = []
        ).

    conjunction_chunk([Conj-conjunction|ATs], ATs, Conj-conjunction).

Which shall be read as “first parse a command followed by its argument, then if the arguments are followed by a conjunction, recursively parse the rest of the list”. The command chunk is slightly more involved since we have to deal with variants of commands.

    %% NAME:
    %%  command_chunk(+AtomTags, -Remainder, -Command)
    %% DESCRIPTION:
    %% True if Command is the command parsed from the atoms and their
    %% tags in AtomTags. The remainder, i.e. the chunk after the
    %% command, is stored in Remainder.
    command_chunk(ATs, ATs1, C) :-
        %% First find a verb, i.e. a potential command.
        list::append(_, [C0-verb|ATs1], ATs),
        %% Then check whether or not the verb is a variant of a known
        %% command.
        game_logic::variants(C, Cs),
        list::member(C0, Cs).

Note the use of append/3 to ignore everything in the list up to a verb. When parsing the arguments we scan the input and look after atoms of the correct type.

    %% NAME:
    %%  argument_chunk(+AtomTags, +Command, -Remainder, -Args)
    %% DESCRIPTION:
    %% True if Args are the arguments corresponding to the arity of
    %% Command with respect to the atoms and their tags in
    %% AtomTags. The remainder, i.e. the chunk after the last
    %% argument, is stored in Remainder.
    argument_chunk(ATs, C, ATs1, Args) :-
        game_logic::command(C, Tags),
        matches(ATs, Tags, ATs1, Args).

    %% NAME:
    %%  matches(+AtomTags, +Tags, -Remainder, -Args).
    %% DESCRIPTION:
    %%  True if the list of atoms and their corresponding tags matches
    %%  Tags, i.e. there exists a sequence of atoms, not necessarily
    %%  in a a direct linear sequence, such that their tags can be
    %%  mapped to the tags in Tags.
    matches(ATs, [], ATs, []).
    matches(ATs, [T|Ts], Remainder, [A|As]) :-
        list::append(_, [A-T|ATs1], ATs),
        matches(ATs1, Ts, Remainder, As).

That’s all the constructs that we’re going to support at the moment. Two remarks should be made before we move on:

  • The chunk predicates can be rewritten as DCGs instead since they’re essentially just threading state. I’ll leave this as an exercise to the reader!
  • argument\_chunk/4 is given the ability to ignore everything that it can’t make sense of. While this is good in many circumstances, it also has the effect that some ill-formed sentences will be incorrectly parsed. For example, consider the sentence “eat the bnana and look at the room”. Assuming that bnana is tagged as unknown, the sentence will be parsed as eat-room since room is the only entity that argument\_chunk/4 discovers. One possible solution is to restrict the argument parsing to the current clause and disallow it to continue past conjunctions.

Putting everything together

Now we’re able to dissect the meaning of the user input and extract commands from it. The next task is to actually carry out the commands and update the state of the game world, but for the moment we’re just going to print the parsed commands to verify that everything works. The steps are the following:

  • Read a line and convert it to atoms.
  • Tag the atom list.
  • Resolve the pronouns.
  • Parse the resulting list of tagged atoms.

And it’s rather easy to cobble together.

    init :-
         write('Welcome to Bacchus-Bosch!'), nl,
         current_input(S),
         repl(S, []).

    repl(S, History) :-
        write('> '),
        nlp::parse_line(S, Atoms),
        write('The input is: '),
        meta::map([X] >> (write(X), write(' ')), Atoms), nl,
        nlp::tag_atoms(Atoms, AtomTags),
        write('The tagged input is: '),
        meta::map([X] >> (write(X), write(' ')), AtomTags), nl,
        (   eval(History, AtomTags) ->
            true
        ;   write('I''m sorry, Dave. I''m afraid I can''t do that'),
            nl
        ),
        repl(S, AtomTags).

    eval(History, AtomTags) :-
        nlp::resolve_pronouns(History, AtomTags, AtomTags1),
        eval_commands(AtomTags1).

    eval_commands(AtomTags) :-
        nlp::parse_atoms(AtomTags, _, Commands),
        write('The parsed commands are: '), nl,
        meta::map([X] >> (write(X), nl), Commands).

If we feed this program with the example sentences we end up with the following dialogue:

Welcome to Bacchus-Bosch!

> look

The input is: look
The tagged input is: look-verb
The parsed commands are:
look-[]

> look at the banana

The input is: look at the banana
The tagged input is: look-verb at-preposition the-article banana-entity
The parsed commands are:
look-[banana]

> eat it

The input is: eat it
The tagged input is: eat-verb it-pronoun
The parsed commands are:
eat-[banana]

> grab the banana and eat it

The input is: grab the banana and eat it
The tagged input is: grab-verb the-article banana-entity and-conjunction eat-verb it-pronoun
The parsed commands are:
take-[banana]
eat-[banana]

> fling feces around the room

The input is: fling feces around the room
The tagged input is: fling-unknown feces-unknown around-preposition the-article room-entity
I’m sorry, Dave. I’m afraid I can’t do that

Source code

The source code is available at https://gist.github.com/862464.

Due to a hefty amount of school-work (I should actually be crunching theorems in number theory right now!) part 3 will probably be delayed one or two weeks.

An Adventure Game – Part 1

A Prolog programmer walks into a bar:

– Can I have beer?

– No.

As promised, in this and the following posts I’ll design and implement a simple, text-driven adventure game in the spirit of Zork. I shan’t be too concerned with superfluous features and instead direct most energy towards nifty algorithms and reasonably well-designed data structures. No guarantees whatsoever will be made regarding the actual playability of the final product! Since they say that a picture is worth more than a thousand words:

Wait. That’s probably not true in the case of a text-adventure game. Crap. In any case the basic ideas involved are not too hard to grasp. The only interface against the user is text in the form of output and input. Output is as one might expect one of the easiest parts to implement since all game objects will have textual descriptions. Input is far, far worse since we’ll be dealing with natural instead of formal languages. In the general case perfect natural language processing is more or less impossible. This is why almost all successful services that make use of natural languages are based on statistical/probabilistic methods instead of strictly formal models such as context-free grammars (hybrids also exist). But of course, just because something is very hard in the general case doesn’t necessarily imply that it’s just as hard in every case. We will however be forced to make some severe restrictions regarding what kind of input we want to accept and focus on these areas.

Where to start? UML-diagrams? Activity diagrams? Of course not — we’ve already put several minutes into the project without savoring a single cup of the brown, precious liquid known to man as coffee. That’s the first step. The second step is to blankly stare into the monitor for at least a few minutes and realize that it would probably be a good idea to put on some music before the mind-numbing silence quells all remaining sanity. Good choices are Einstürzende Neubauten, Melt Banana or Programmer Art, by Yellow Bear. The fourth step is to automatically generate a nonsensical name for the project. I used a soundex-algorithm with random names as input, and after some tinkering I ended up with:

Bacchus-Bosch

No, I’ve got absolutely no idea what it means, but it rolls of the tongue nicely. Now we’re finally in a position where we might be inclined to do some real work! This is an instance where the bottom-up methodology will work nicely: start with something simple that we know that we’ll need later on and expand from there. For no particular reason I’ll start with the most fundamental parts of user input: tokenizing and part-of-speech tagging. A typical example of user input is:

open the door

go through the door

How should these sentences be construed? Well, no matter what we’ll have to start by reading them character by character from an input stream. This will result in a list of characters. We can code this in more or less the same way as in an imperative language: continue reading characters until the end of line is reached.

read_line(S, Chars) :-
    get_char(S, C),
    read_line(C, S, Chars).

read_line('\n', _, []) :- !.
read_line(C, S, [C|Chars]) :-
    read_line(S, Chars).

Where get\_char/2 takes a stream as input and returns the next character. We could in theory analyze this character list already at this stage, but for simplicity it’s better to introduce some additional pre-processing steps. Therefore we’ll take our character list and group together the characters into words instead. For example, the character list from the first example sentence would be [o,p,e,n,'\,',t,h,e,'\,',d,o,o,r],  and would result in the word list [open, the, door]. There already exists a primitive for this purpose: atom\_chars/2, so what we need to do is to go through the list and look for groups separated by whitespace and convert each group to an atom. One simple solution is to use a set of DCG-rules (for brevity some basic rules are omitted):

chars_to_list([A|As]) -->
	chars_to_atom(A),
	whitespace,
	chars_to_list(As).
chars_to_list([A]) -->
	chars_to_atom(A),
	opt_whitespace.
chars_to_atom(A) -->
	chars(Cs),
	{atom_chars(A, Cs)}.

The goal in the curly braces, atom\_chars(A, Cs), makes sure that each group is converted appropriately. This is certainly not the most efficient solution. For example: the last atom always needs to be parsed twice in chars\_to\_list//1, one time in the first rule and one time in the second. In a real compiler this might not be acceptable, but since we’re dealing with sentences of just a few words it’s A-OK.

Now we can recognize individual words, but we still don’t know what they mean, i.e. what semantic class they belong to. Are they imperative commands? Directions? Physical objects? For that we’ll use a technique that in natural language processing is known as tagging: each word will be assigned a tag corresponding to its lexical category. For example, the sentences above could be manually tagged as:

open/verb the/article door/noun

go/verb through/preposition the/article door/noun

Don’t fret if the part-of-speech lectures from middle school are nothing but a distant, hazy memory: it won’t become much more complicated than this. Like all other domains in natural language processing, tagging is very hard to do perfectly. Therefore we shall use a simple tagger that either looks up the tag for a word manually, or forms a decision based on the previously tagged words. First we need a small dictionary that contains words and their lexical categories. The simplest solution is to implement it as a set of word/2 facts:

:- object(game_logic).

    :- public(word/2).

    word(entity, door).
    word(entity, key).
    word(entity, banana).

    word(direction, north).
    word(direction, east).
    word(direction, south).
    word(direction, west).

    word(preposition, on).
    word(preposition, through).

    word(pronoun, he).
    word(pronoun, it).
    word(pronoun, she).

    word(verb, go).
    word(verb, take).
    word(verb, open).
    word(verb, eat).
    word(verb, use).

    word(article, a).
    word(article, an).
    word(article, the).

:- end_object.

A remark: it would be preferable to store the tuples with the arguments switched to exploit first-argument indexing, since the word is usually looked up more frequently than the lexical category. Obviously this is just a sample dictionary, but it can easily be extended once we begin working on the rest of the game. Next we’ll need a predicate that, given a word returns its lexical category as a tag. However, since we also want to be able to construct rules that takes the history into account, it will in addition to the word also need a list of the preceding words and their tags. For efficiency reason this list will be stored in reversed order. An example of such a rule is: “if the previous tag was an article, then the word must be an entity”.

    %% NAME:
    %% 	tag(+Preceding, -Word, -Tag).
    %% DESCRIPTION:
    %% 	True if Tag is the tag corresponding to Word. Preceding is used
    %% 	whenever a rule needs to look at the history in order to tag the
    %% 	word.
    tag([_-article|_], _, entity).
    tag(_, A, T) :-
        game_logic::word(T, A).

It’s easy to extend tag/3 with additional rules, but let’s leave it as it is for now. The actual tagger, tag\_atoms/2, will just go through the list of atoms and call tag/3 for each of them.

    %% NAME:
    %%  tag_atoms(+Atoms, -AtomTags).
    %% DESCRIPTION:
    %%  True if AtomTags is a list of pairs of the form Atom-Tag,
    %%  where Tag is the tag corresponding to Atom.
    tag_atoms(As, Ts) :-
        tag_atoms(As, [], Ts).

    tag_atoms([], _, []).
    tag_atoms([A|As], Pre, [A-T|Ts]) :-
        tag(Pre, A, T),
        tag_atoms(As, [A-T|Pre],Ts).
    tag_atoms([A|As], Pre, [A-unknown|Ts]) :-
        %We don't use a cut since we want the ability to try several
        %different tags if necessary.
        \+ tag(Pre, A, _),
        tag_atoms(As, [A-unknown|Pre], Ts).

Note something about tag\_atoms/3: it can return several solutions if tag/2 is non-deterministic. This is actually a good thing since natural language is inherently non-precise and ambiguous. If some other part in the game fails due to an erroneous tagging it’s always possible to backtrack and try again.

Here’s how the tagger looks in action:

-> eat the key
The input is: eat the key
The tagged input is: eat-verb the-article key-entity

-> open the door with the banana
The input is: open the door with the banana
The tagged input is: open-verb the-article door-entity with-preposition the-article banana-entity

Whether those specific commands make any sense in the finished game remains to be seen!

Summary

We’ve implemented some fundamental parts of Bacchus-Bosch and are now able to get input from the player and make sense of it by tagging it. Next we’ll concern ourselves with parsing. The goal is to construct a parse tree from the tagged input that reflects the structure of the command that the player had in mind. Stay tuned!

Source code

The source code is available at https://gist.github.com/847541.

A Crash Course in Logtalk

Or: Logtalk as she is spoke.

Since the last post was quite theoretical it’s only fair that the following ones will be more pragmatic in nature. The goal will be to develop a simplistic but still fairly capable text-adventure game in the same spirit as Zork and its successors and present the parts incrementally. But as you, the reader, probably knows compatibility between various Prolog systems is spurious at best. One remedy which I’ve championed before is Logtalk – an “open source object-oriented logic programming language” developed by Paulo Moura, which allows one to write portable programs without worrying about the details of the underlying Prolog system. As the description suggests, Logtalk leaves the constricted domain of a logic program and introduces a few new concepts that can greatly aid the programmer not only in large, but small and medium-sized projects. The question of what an object is in the context of logic programming is an interesting one. We shall however not concern us ourselves by giving any formal definitions and instead be rather descriptive. A formalistic viewpoint will probably be perused in a later entry, but for now the reader can refer to for example Logic and Objects, by Francis G. McCabe, which contains a thorough entry on the semantics of the Logic and objects language and answers what inheritance and objects mean in logic programming. Hence the remainder of this post will try to shed some light on the basics of the Logtalk language and explain how it’s installed and used. More advanced concepts will be explained as they are used when the time is ripe.

Installation

We begin our journey by downloading the Logtalk distribution. This can be done either via the Logtalk download page or by Subversion – the choice is yours! The next step is to read the exhaustive INSTALL.txt file, but for a POSIX system the procedure is as follows:

  • Set the correct environment variables. Logtalk uses two variables: LOGTALKHOME and LOGTALKUSER. For a single-user system these can coincide to the same directory, e.g. $HOME/lgtsvn, or wherever the distribution was unpacked. It’s also a good idea to augment the $PATH and $MANPATH variables to include $LOGTALKHOME/scripts, $LOGTALKHOME/integration and $LOGTALKHOME/man respectively.
  • Run the correct script in $LOGTALKHOME/integration. For SWI-Prolog this is swilgt.sh, for YAP Prolog it’s yaplgt.sh.

That’s it! Of course one may also digress in various customization aspects, but for basic usage this is more than enough.

Usage

Let’s hack away. I shall refrain from giving the idiomatic but ultimately quite meaningless Hello World-example and instead present something that uses at least some of the basic Logtalk facilities. The problem is the following: compute the bottom-up closure of a propositional logic program. If you’ve read the last entry on the semantics of logic programs you should immediately realize that this is nothing else than the least Herbrand model. We begin by outlining the algorithm:

  • The facts in the program are true.
  • If there is a rule H \leftarrow B_1, ,,, B_n such that all B_i are known to be true, then H must be true.
  • If it’s impossible to collect any new information, we’ve reached a fixpoint and are done.

The first step is to choose a program representation. Rules shall be represented as facts of the form rule(Head, Body), where Body is a list [B_1, ..., B_n] and Head and B_i are atoms. For facts, Body = [].  For example:

rule(a, []).
rule(b, [])

rule(c, [a,b])

Which should be read as: a and b are true, and if a and b are true then c must be true. This brings us to our first Logtalk concept: the object. The rule set discussed above could written as:

:- object(database).

    :- public(rule/2).

    rule(a, []).
    rule(b, []).

    rule(c, [a,b]).

:- end_object.

There’s nothing really fancy going on. The :-\, object directive obviously denotes the start of an object, while the :-\, end\_object directive denotes the end. public(rule/2) means that the set of rule/2 clauses have public visibility, i.e. that they can be accessed from anywhere. The only possible source of confusion might be the loose use of the word object. In e.g. Java or C++ there’s a sharp distinction between a class and an object. We say that an object is an instance of a class. This distinction is needed due to the fact that objects have explicit, dynamic state. In Logtalk, however, objects are most often used to provide module-like namespaces. (To be fair, there exists dynamic objects but they should be used sparingly, just like assert/retract in Prolog). Hence there’s often no need to make a distinction between a class and an object. For a more thorough explication, see the relevant part of the Logtalk manual.

Now let’s turn to the algorithm. From the pseudo-code we know that we’ll need a predicate that takes the current set of atoms known to be true and collects the heads of all the satisfied rules. This is easy to do: if we encounter a rule with the head H and body B, such that B is currently satisfied, then add H to the set of new inferences. Since there already exists a library for ordered sets in Logtalk we can write it as:

next(I0, I) :-
    setof(Head,
            (
             Body^(database::rule(Head, Body),
             satisfied(Body, I0),
             \+ set::member(Head, I0))
            ),
            New),
    set::union(I0, New, I).

The ::-operator denotes message sending. Hence, when we want to call a predicate defined in the database we write database::rule(...), but when we want to call a set predicate we prefix it with set.  I is the union of the old set of inferences, I0, and the new set of inferences, New. A head Head of a rule is added to New if its body is satisfied and it hasn’t been collected before. Since we’re only dealing with propositional atoms, the satisfied/2 predicate is easily implemented as:

satisfied(Body, Atoms) :-
    set::subset(Body, Atoms).

Next we need a predicate that repeatedly calls next/2 until no new inferences can be made. Since we use setof/3 in next/2, it will simply fail if New is the empty set. Hence the iteration only needs an if-then-else construct that either unifies its last argument with the obtained set of inferences, or calls itself recursively.

iterate(I0, Fixpoint) :-
    (   next(I0, I) ->
        iterate(I, Fixpoint)
    ;   Fixpoint = I0
    ).

To wrap it up it might be nice to have a predicate that takes a goal as argument, calls iterate/2 and checks whether the goal is a member of the fixpoint or not.

:- public(prove/1).

prove(Goal) :-
    iterate([], Fixpoint),
    set::member(Goal, Fixpoint).

Putting everything together

Logtalk programs are loaded with logtalk\_load/1 or logtalk\_load/2. Assuming that the bottom-up procedures were included in an object with the name bup, the whole project is loaded with the sequence:

logtalk_load(database). %The database.
logtalk_load(library(types_loader)) %The set library.
logtalk_load(bup) %The main program.

To run a query, one writes:

?- bup::prove(X).
X = a n
X = b n
X = c n
false.

And since it’s a mouthful to manually load the files every time it’s better to put that information in a loader file named loader.lgt.

:- initialization((
    logtalk_load(library(types_loader)),
    logtalk_load(database),
    logtalk_load(bup))).

The loader file can then be loaded from the top-level with either logtalk_load(loader) or the shorthand {loader}.

That’s it for now. I’ll admit that it would be nice to attach the full source code directory, but unfortunately the free WordPress hosting doesn’t seem to have that functionality. I managed to upload a zip-file by changing the file extension, but that hardly seems ideal. Rest assured that the matter will probably be solved before the next entry!

A Gentle Introduction to Herbrand Models

Almost related pun of the day: Some interpretations are more equal than others.

I’ve not yet encountered a single person — including myself — who have grasped the concept and utilities of Herbrand interpretations at a first glance. This might lead one to believe that the theory is so hard and abstract that it’s not really related to every day logic programming anyway, but nothing could be further from the truth. On the contrary, the problem is rather that the definition of a Herbrand interpretation is too simple to make any sense — a wolf in sheep’s clothing. Hence we have a good subject at hand and a splendid opportunity for me to confuse you further with deceptive didacticism.

A logic program is a finite set of rules and facts. Let’s not bother ourselves by giving a formal definition and instead cut right to the chase with an example:

natural(zero).
natural(s(N)) \leftarrow natural(N).

From a pragmatic perspective it should be construed as: zero is natural (i.e. a natural number), and if it is known that N is a natural number, then it’s the case that s(N) is a natural number. I’ll be the first one to admit that it’s not a very interesting program, but it’ll have to do for the moment. Following this intuition it’s possible to answer queries to the program in two different ways: top-down and bottom-up. Let our query be natural(s(zero)). Here’s how the two different strategies differ:

Top-down

To solve natural(s(zero)), we unify natural(s(zero)) with natural(s(N)) and obtain the unifier \{N= zero\}. Then we recursively solve the new goal obtained from the right-hand side of the rule: natural(zero). This can be done in one step, and since there are no more goals to resolve we’re done.

Bottom-up

We begin to note that natural(zero) holds. A solid start! Then, since the body of the second clause is true with the unifier \{N= zero\} (the same as before), we conclude that natural(s(zero)) must also be true. Since this is the same as the original query there’s no reason to continue.

I’ve admittingly danced over a lot of intricate details, but I should at least mention that the top-down approach corresponds to SLD-resolution while the bottom-up approach corresponds to unit-resolution (sometimes called hyper-resolution). The difference between the two lies in the application of the resolution rule: in SLD-resolution we produce resolvents between a head of clause and a goal clause, in unit-resolution we produce resolvents between a unit-clause and the body of a clause. So we have two ways of answering a query, but how do we know that they are correct? For that we need to backtrack (pun not intended) and carefully explicate the meaning of the program. This is formally done with a model. The content of this particular program is:

  1. A single constant: zero.
  2. A single function symbol of arity 1: s.
  3. A single predicate symbol of arity 1: natural.

And to provide a meaning to the program we need to explain exactly what these symbols mean. We need two functions: one for the constant symbol, f_{zero}, and one for the function symbol, f_s. In the domain of the natural numbers these can be defined as:

  1. f_{zero}(zero) = 0
  2. f_s(N) = N + 1

Which may then be combined into a single function, f, that allows us to recursively compute the value of any term in the program. It is defined as:

f(zero) = f_{zero}(zero)

f(s(N)) = f_s(f(N))

For example:

f(s(zero)) = f_s(f_{zero}(zero)) = f_s(0) = 0 + 1 = 1

The only predicate symbol, natural, must be mapped to a relation on the domain. The simplest such is just the set \{0, 1, ...\}. And we’re done with this particular model.

Is it a good model? That depends. In the context of our logic program it seems to be a bit overkill. Previously we only had to worry about the symbols that actually appeared in the program: s, zero and natural; but now we’ve introduced arithmetical notation that so to speak goes beyond the original interpretation. There’s really no reason at all to demand that zero must be evaluated to 0 and that s(zero) must be evaluated to 1. They are just two different representations. With this in mind we can construct a simpler model:

  1. f_{zero}(zero) = zero
  2. f_s(N) = s(N)

And in the same vein as before this may be combined into a single function f. Applied to the same term as before we obtain:
f(s(zero)) = f_s(f_{zero}(zero)) = f_s(zero) = s(zero)

We’re back with what we started with! This means that the terms in the program are just mapped to themselves, and why not? The predicate symbol natural will now be mapped to the relation \{zero, s(zero),...\} instead of \{0, 1, ...\}.

These kinds of models are known as Herbrand models. The general definition closely mimics the earlier one, with the effect that all terms are mapped to themselves and that predicates are mapped to relations over the universe of terms (the Herbrand universe). Since the only interesting part of a Herbrand model is the mapping of predicates, it’s often presented as a set that enumerates the values for which the predicates should be true. In our example, which is in fact a least Herbrand model, this was \{natural(zero), natural(s(zero)), ...\}. As should be evident by now this is precisely the set that we already had in mind as programmers, it’s the intended meaning of the program.

But was this just a fluke? Could there be cases where it’s impossible to find a Herbrand model even though there’s exists another model? Fortunately the answer is no: if there exists a model for a logic program then there also exists a Herbrand model. This provides a theoretical justification for both SLD- and unit-resolution. In the first case we use this in our search for unsatisfiable sets of ground clauses from the Herbrand universe, in the second case we actually build the (least) Herbrand model from bottom up.

Prolog

And with that awful pun, we’re off.  The good news is that it can only get better from here. While I can’t claim to have any grand plans regarding the content of the blog, my aim is to cover both practical and theoretical issues in the realm of logic and logic programming. From this premise, it immediately follows that the title “The blogging of logic programming” probably would have been a more accurate name of the blog, since I’ll probably leave the constricted domain of Prolog quite often. Oh well.

I’ll not make any special assumptions when it comes to the knowledge level of the reader, but I’ll try to keep a didactic and pedagogical approach for the simple reason that I probably wouldn’t understand a post once the coffee-induced frenzy wore off otherwise.