Forays into clojure.core.logic

22 June 2014 - status: draft

This section contains explorative usages of clojure.core.logic. Nothing described herein should be taken as fait accompli but rather as ongoing search for the right place of clojure.core.logic in the toolset.

The problem

This article is based on my efforts to transcribe the rules of the 7 Wonders board game into Clojure. 7 Wonders is overall a relatively straight forward game, complexity lies mainly in individual card rules, especially on the wonder boards, that create one-off logic relationships.

Why clojure.core.logic?

Initial attempts to write a game engine highlighted the complexity of choosing an appropriate Clojure data model for the various pieces (wonder, boards, cards, resources, players). Undoubtedly, these can be solved by careful object-oriented modelling. After all all the main concepts are concrete game items linked by logical relations. However, this approach seemed unsatisfactory in at least one aspect: data representation and data access paterns through Clojure data navigation were linked at the hip.

For example, representing players we want to be able to identify the wonders board held by a player and also the current set of built structures as well as cards in hand. Players themselves need to be linked via their seating order. As a functional language all these structures are immutable. The simplest representation would be treat them all as nested structures, i.e. the game is made up of, amongst others, a list of players in seating order, each player map contains a slot for the board and also a list of buildings etc. This works well enough for a while but eventually a lot of code is spent traversing hierarchies, to find the science buildings of a neighbour one needs to have the neighbours (from the game map) and then traverse through their building lists. Worse to find the tradeable resources of neighbours one needs to look not just at the structures built but also at the wonders board. The navigational aspects of how to access this data clouds over the logical relations of neighbour seating and possession, which are the underlying game aspects to be expressed.

Enter clojure.core.logic: the promise, other than the general promise of logic programming to be able to run program forwards and backwards, it brings database relational model to in memory data representation, without the need of an actual database. The relational model and relation access are immensely powerful tools eliminating most of the complexities around navigation of data (wtih some efficiency trade-offs). However, rather than being constrained by a straight-jacked SQL interface an in-program relation representation allows free interleaving of relational logic and Clojure primitive functions where necessary.

Relational versus hierarchical data

Hierarchical data complects data with navigation
- Data structures are linked by access considerations
- Logical data are grouped differently (although potentially linked by common interfaces, is-a relations) into objects for navigation
Relational data thrives on normalization, i.e. clean separation of underlying atomic concepts
- Data navigation is abstracted in the relational engine (database or core.logic relational engine)
- Normalization allows representation of common features in the same table, for example point bearing structures are in one relation, cost-bearing structures in another etc. Collection of items sharing one relation can be accessed as one.

Although the relational model is powerful there are a number of drawbacks to be considered

The decision points for encapsulation, information hiding and generally beating the Law of Demeter are less clear. By default relational facts are global and flat (i.e. not grouped and clustered into coherent units).
A follow on from the previous, but worth mentioning on its own: logical statefulness as required by the model is introduced into the global namespace leading to might be deemed global state (yuk).

Managing state

In most worthwhile programs there is a smattering of state to be maintained and updated. Keeping in the tradition with Clojure statefulness in core.logic is pushed as much to the outside as possible. In fact there are no state manipulating primitives in the core functions at all. Instead all state is an artifact of modifying the immutable Clojure datastructures making up the core.logic.pldb databases. How does one use this to implement the bits of state required?

For the context of the 7 Wonders implementation I have gone down the route to keep all state in the core.logic database, itself kept in one of Clojure's stateful primitives (say an atom for simplicity). State manipulation then is to transform one snapshot of the database into the next, which can be achieved in logic without resorting to many non-relational primitives. To start with we define the concept of an action goal to have the form below where the initial input-state is intended to the be the same state that we are running logic on. Later on it may progressively diverge as we add more effects of a single action. We must take care then to re-snapshot it after any change that might influence further logic derivations.

(predicate input-state ... parameters ... output-state)

At the most simple let's define two simple state mutators to add and retract atomic facts. For the moment these are non-relational and in addition depend on extending the core IWalkTerm interface to correctly deal with sets.

(defn facto [instate fact outstate]
  (project [instate fact]
           (== outstate (apply db-fact instate fact))))

(defn retracto [instate fact outstate]
  (project [instate fact]
           (== outstate (apply db-retraction instate fact))))

Now in anticipation of dealing with strings of these primitive state mutators, we also will need a way to write action chains without introducing dozens of one of lvars for intermediate results. Hence the following macro, which in spirit similar to Clojure's threading macros creates the appropriate lvars for a chain of actions and weaves them through the supplied predicates (assuming the standard action for of input-state first and output-state last in the parameter list):

(defmacro chain-actions [& args]
  (let [actions (rest (butlast args))
        instate (first args)
        outstate (last args)
        tempstates (repeatedly (dec (count actions)) #(gensym "state"))
        all-states (concat [instate] tempstates [outstate])
        
        enriched-actions
        (map
         (fn [a [sin sout]]
           (list* (first a)
                  (concat [sin] (rest a) [sout])))
         actions
         (partition 2 1 all-states))]
    `(fresh [~@tempstates]
            ~@enriched-actions)))

With these tools under our belts let's now define what are possible the simplest game actions: transfering resources from a player to another player or the bank as well as the discard action netting three gold.

(defn transfero
  [instate payer receiver transfer outstate]
  (fresh [payer-state] 
         (conde [(== payer :Bank) (== payer-state instate)]
                [(fresh [res new-res] 
                        (resources payer res)
                        (rembero-all transfer res new-res)
                        (chain-actions instate
                                       (retracto [resources payer res])
                                       (facto [resources payer new-res])
                                       payer-state))])
         (conde [(== receiver :Bank) (== outstate payer-state)]
                [(fresh [res new-res]
                        (resources receiver res)
                        (appendo res transfer new-res)
                        (chain-actions payer-state
                                       (retracto [resources receiver res])
                                       (facto [resources receiver new-res])
                                       outstate))])))

(defn discardo [instate player card outstate]
  (chain-actions instate
                 (transfero :Bank player [:Gold :Gold :Gold])
                 (retracto [hand player card])
                 (facto [discarded card])
                 outstate))

Challenges around logic programming

In addition to positives there are also some unique struggles with regard to logic programming, especially the pursuit of the pure form eschewing conda, condu, project and other non-relational constructs.

Limited negation

Even though relational predicates are the most versatile ones a lot of logic has, in my own usage at least, been one way. The lack of negation support leads to problems that are fairly unique and coming from mainstream Clojure or Java simply incomprehensible. To take an example, 7 Wonders contains the rule that a player can only build any building once. A simple translation of this would be the rule that a building is not buildable if it has already been built. To translate this into the logic form I eventually stuck with a condu interpretation that makes the whole buildable construct non-relational.

(condu 
  [(building player card) fail]
  ["... success case do other checks ..."])

Polymorphism and pluggability

One of the main forms of flexibility and extensibility of many modern languages is the support for plug points - be it interfaces with polymorphic behaviour, be it runtime reflection etc. The pluggability serves narrow goals of segregating the logic of the system via clearly defined API points to actually allowing deploy and runtime extension via third-party contributions. On the logic programming side this seems to be absent as a first order mechanism, particularly the polymorphism taken for granted in essentially all modern programming languages.

Certainly, using the project tool it is not difficult to introduce non-relational pluggability into the system, but it somehow feels like abandoning the promised high road of logic programming.

Encapsulation and information hiding

Similar to the note of polymorphism I am also struggling with satisfying my expectations about encapsulation and information hiding in the logic programming world. Starting with C's abstract data type concept, significant parts of modern software engineering in the imperative and object-oriented camp are dedicated to carefully encapsulating data (especially mutable data). The goal is to expose data alongside the applicable operations that maintain invariants of the data as well as to limit visibility of data to a select class of users to reduce the overall connectedness of software systems.

On the logic programming side on the other hand - at least in most examples I came across - information hiding is not considered at all. Facts are generally globally available and though they are (thank God) not stateful, it still represents a gross violation of the Law of Demeter. Certainly, in the core.logic implementation it is entirely possible to scope facts and predicates by Clojure namespaces, but this is not a feature often discussed and given the implementation of data as global Clojure maps not strongly enforced.