Adjusting direction

I have blogged about miniKanren in general and specifically Adderall various times. While I still love the concept and idea behind the language, I have concluded that I’m not good enough with the language to actually write anything really productive. Thus, I’m going to set it aside and not use it for parts of the AI routines for pyherc. I still have the Reasoned Schemer on my desk and I plan to keep on learning the language, but I’m going to do it in separate projects and not as part of pyherc.

This of course means that now I have to come up with something that is:

  • small
  • interesting
  • fun

I don’t know yet what it’ll be, but I’m confident that I’ll find something. Might even be something funny like macros that build code and reason about output based on miniKanren code.

Wishful coding: Adderall, traps and items

I have been pondering over some ideas about traps, items and how to represent what kind of effects they have in-world. I might be over thinking this a bit and going for too general and flexible solution, when simpler solution would work just fine. Currently this isn’t that urgent yet, as there are only few monsters and two types of traps (pits and caltrops). Monsters are too stupid to avoid either one. For caltrops it sort of makes sense, but they really should be able to spot huge pits and go around.

Continue reading

Manipulating levels in Adderall

So, I have a goal: I wish to be able to reason and manipulate levels in Adderall (a miniKanren implementation in Hy). First step is to start with floors and walls. Here is our simple level:

{:wall-data {(, 5 5) :rock-wall
             (, 6 5) :rock-wall
             (, 7 5) :tile-wall}
 :floor-data {(, 5 6) :dirt-floor
              (, 6 6) :rock-floor
              (, 7 6) :rock-floor}}

Since I don’t yet know how to manipulate dictionaries, I’ll transform this into list of lists:

[[:wall-data [(, (, 5 5) :rock-wall)
              (, (, 6 5) :rock-wall)
              (, (, 7 5) :tile-wall)]]
 [:floor-data [(, (, 5 6) :dirt-floor)
               (, (, 6 6) :rock-floor)
               (, (, 7 6) :rock-floor)]]]

In order to manipulate walls and floors, we need to have access to them in the datastructure. For walls, I wrote the following:

(defn wall-dataᵒ [level wall-data]
  (fresh [x]
    (≡ x [:wall-data wall-data])
    (memberᵒ x level)))

First, a fresh variable x is introduced. The x is unified with a list that has first item as :wall-data (a keyword) and rest is wall-data parameter. The final step is to say that x should be found in level (again supplied as a parameter). Floor-data is retrieved in the same way:

(defn floor-dataᵒ [level floor-data]
  (fresh [x]
    (≡ x [:floor-data floor-data])
    (memberᵒ x level)))

Now that we have access to correct part of the datastructure, we can start manipulating it:

(defn wallᵒ [level location id]
  (fresh [data tile]
    (wall-dataᵒ level data)
    (≡ tile (, location id))
    (memberᵒ tile data)))

wallᵒ takes three parameters, first is the overall datastructure, second is location we are interested in and third one is the ID of tile in that location.

Two fresh variables are introduced: data and tile. wall-dataᵒ is then used to drill down to correct position of the data structure and associate data with wall-data information. Then we unify tile with a tupple that consists of location and id and say that this tupple should be part of the data. Again, floor is handled in the same way:

(defn floorᵒ [level location id]
  (fresh [data tile]
    (floor-dataᵒ level data)
    (≡ tile (, location id))
    (memberᵒ tile data)))

Now we have the tools that we need at this point. But how are we going to use them? Lets first create a variable and assign some data into it:

(setv level-data 
  [[:wall-data
    [(, (, 5 5) :rock-wall)
     (, (, 6 5) :rock-wall)
     (, (, 7 5) :tile-wall)]]
   [:floor-data
    [(, (, 5 6) :dirt-floor)
     (, (, 6 6) :rock-floor)
     (, (, 7 6) :rock-floor)]]])

Easy way to use these functions is to query what is in given location:

=> (run* [q]
     (wallᵒ level-data (, 6 5) q))
[:rock-wall]

Looks simple enough. At (6 5) there is :rock-wall.

How about asking for all locations that have :rock-floor?

=> (run* [q]
     (floorᵒ level-data q :rock-floor))
[(6, 6), (7, 6)]

Similar query than before, but with q at different position.

To check if a given location has a specific type of floor, we can use following two examples:

=> (run* [q]
     (floorᵒ level-data (, 5 6) :dirt-floor)
     (≡ true q))
[True]

=> (run* [q]
     (floorᵒ level-data (, 6 6) :dirt-floor)
     (≡ true q))
[]

The first goal associated level-data, given location and given floor type together. If this association succeeds, q is unified with true in the second line. If association fails, q is not unified and an empty list is returned as a result.

What about retrieving locations of the floor tiles and their IDs?

=> (run* [q]
     (fresh [location id]
       (floorᵒ level-data location id)
       (≡ (, location id) q)))
[((5, 6), :dirt-floor), ((6, 6), :rock-floor), ((7, 6), :rock-floor)]

We first introduce two fresh variables and associate them with level-data using floorᵒ. Then we unify q with a tupple that consists of location and id (we can always return just a one variable, thus we need to perform this extra step). Because we used run*, all found results are returned. We could have limited the amount to 2 by doing run 2 [q], instead of run* [q].

A little more complex (and pretty useless at this point) is shown next:

=> (run 1 [q]
    (wallᵒ q (, 1 1) :rock-wall)
    (floorᵒ q (, 1 2) :dirt-floor)
    (floorᵒ q (, 1 3) :dirt-floor)) 
[([:wall-data ([[1 1] :rock-wall] . <'_.0'>)]
  [:floor-data ([[1 2] :dirt-floor] [[1 3] :dirt-floor] . <'_.1'>)] . <'_.2'>)]

“if we have :rock-wall at (1 1) and :dirt-floor at (1 2) and (1 3), what would the level look like?” Here we are interested only in one answer (thus run 1 [q]). Since the lists we are dealing with could have more entries in addition to the ones that we specified, there are fresh variables shown: <‘_.0’>, <‘_.1’>, <‘_.2’>. These could be anything, they don’t affect to the validity of the result.

All this is still at very basic level. We have created goals that define overall data structure of levels and specific data structures of walls and floors. With these 4 goals we can query, check and create levels. More interesting this will be after we add monsters and traps into mix and are able to specify their spatial relations (there is a monster standing in between a wall and a pit). At that point we would have simple tools that can be used to aid placing things during level generation or that can be used by character AIs to reason their surroundings.

adderall and funny characters

Take a simple minikanren program like:

(run* [q]
  (fresh (x y)
    (appendᵒ x y ["a" "b" "c" "d"])
    (≡ (, x y) q)))

There are some special characters there, that are normally somewhat hard to type. Of course, it is possible to use easy to type function names and the program would look like:

(run* [q]
  (fresh (x y)
    (appendo x y ["a" "b" "c" "d"])
    (unifyo (, x y) q)))

But if you’re like me and would like to use the forms in shown in the upper program, you have to figure out something else.

Since I’m using emacs when working with lisp, I have abbrev-mode in my disposal. I can type the code as shown in the second listing and emacs automatically transforms it to the one shown in the upper one.

For time being, I have following definition in my abbrev_defs file (same for inferior-lisp-mode-abbrev-table too):

(define-abbrev-table 'hy-mode-abbrev-table
  '(
    ("alwayso" "alwaysᵒ" nil 1)
    ("anyo" "anyᵒ" nil 1)
    ("appendo" "appendᵒ" nil 1)
    ("conde" "condᵉ" nil 3)
    ("condi" "condⁱ" nil 2)
    ("conso" "consᵒ" nil 1)
    ("emptyo" "emptyᵒ" nil 1)
    ("eqo" "eqᵒ" nil 1)
    ("flatteno" "flattenᵒ" nil 1)
    ("flattenrevo" "flattenrevᵒ" nil 1)
    ("listo" "listᵒ" nil 1)
    ("listofo" "listofᵒ" nil 1)
    ("lolo" "lolᵒ" nil 1)
    ("loto" "lotᵒ" nil 1)
    ("membero" "memberᵒ" nil 1)
    ("memberrevo" "memberrevᵒ" nil 1)
    ("memo" "memᵒ" nil 1)
    ("nevero" "neverᵒ" nil 1)
    ("pairo" "pairᵒ" nil 1)
    ("pmembero" "pmemberᵒ" nil 1)
    ("remembero" "rememberᵒ" nil 1)
    ("resto" "restᵒ" nil 1)
    ("salo" "salᵒ" nil 2)
    ("twinso" "twinsᵒ" nil 2)
    ("unifyo" "≡" nil 2)
    ("unwrapo" "unwrapᵒ" nil 1)
   ))

This is really something cosmetic and has no effect into functionality at all.

Adderall – more appendᵒ and memberᵒ

Lets do something practical this time and design an adventure. Our adventure will be very linear in nature, it starts from one location, progresses through several location, until it reaches the conclusion. There are no loops or branches this time.

Adderall has firstᵒ, that can be used to create a goal stating “a list l, starting with element s”. For example:

(run 1 [q]
  (firstᵒ [1 2 3 4] q))

[1]

This sounds very useful for us, since our adventure has to start from somewhere. Adderall doesn’t seem to have a way to specify similar goal, but for the last item of a list, so we need to define one (lifted from xxx again):

(defn lastᵒ [s l]
  (fresh [a]
    (appendᵒ a [l] s)))

(run 1 [q]
  (lastᵒ [1 2 3 4] q))

[4]

The lastᵒ builds on top of old trusty appendᵒ: something (the fresh variable a) is appended with l, resulting s. Doesn’t look too complicated, but I couldn’t write it by myself and had to resort on checking from Object Commando. Clearly logic / relational programs aren’t as simple to write as I had assumed.

Now we have way to specify start and end of our journey. We would like to specify some parts in the middle too. Rather than specifying their exact locations, we would like to tell that “these two items are next to each other”. And for that, there’s following function:

(defn adjacentᵒ [s l sl]
  (fresh [a b]
    (condᵉ [(appendᵒ a (list* s l b) sl)]
           [(appendᵒ a (list* l s b) sl)])))

There is two ways of satisfying the goal (hence the condᵉ): s comes first, followed by l or l comes first, followed by s. Fresh variables a and b are used to specify parts of the list we are not interested.

Armed with these new functions, we can write following:

(run 3 [q]
  (firstᵒ q :start)
  (lastᵒ q :treasure)
  (adjacentᵒ :treasure :ambush q)
  (memberᵒ :inn q)
  (memberᵒ :stream q)
  (memberᵒ :forest q))

[['\ufdd0:start', '\ufdd0:inn', '\ufdd0:stream', '\ufdd0:forest', '\ufdd0:ambush', '\ufdd0:treasure'],
 ['\ufdd0:start', '\ufdd0:inn', '\ufdd0:forest', '\ufdd0:stream', '\ufdd0:ambush', '\ufdd0:treasure'], 
 ['\ufdd0:start', '\ufdd0:stream', '\ufdd0:inn', '\ufdd0:forest', '\ufdd0:ambush', '\ufdd0:treasure']]

The adventure starts from :start and ends when we reach :treasure. Along the way there is :inn, :stream and :forest. There’s also an :ambush, that is located next to :treasure.

Another example:

(run 3 [q]
  (firstᵒ q :start)
  (lastᵒ q :treasure)
  (adjacentᵒ :treasure :ambush q)
  (adjacentᵒ :inn :stream q)
  (memberᵒ :forest q))

[['\ufdd0:start', '\ufdd0:inn', '\ufdd0:stream', '\ufdd0:forest', '\ufdd0:ambush', '\ufdd0:treasure'],
 ['\ufdd0:start', '\ufdd0:forest', '\ufdd0:inn', '\ufdd0:stream', '\ufdd0:ambush', '\ufdd0:treasure'],
 ['\ufdd0:start', '\ufdd0:stream', '\ufdd0:inn', '\ufdd0:forest', '\ufdd0:ambush', '\ufdd0:treasure']]

Otherwise similar, but now :inn is located near :stream.

The adventure is very simple, very linear and not terribly interesting for the player. But this is already one step above of our previous tests and is starting to look like what I’m after. If I wanted, I could express branches as sub lists:

(run 3 [q]
  (fresh [path]
    (firstᵒ path :hidden-way)
    (memberᵒ :forest-clearing path)
    (memberᵒ :grotto path)
    (firstᵒ q :start)
    (lastᵒ q :treasure)
    (adjacentᵒ :treasure :ambush q)
    (adjacentᵒ :inn :stream q)
    (memberᵒ :forest q)
    (memberᵒ path q)))

[['\ufdd0:start', '\ufdd0:inn', '\ufdd0:stream', '\ufdd0:forest', ('\ufdd0:hidden-way' '\ufdd0:forest-clearing' '\ufdd0:grotto' . &lt;'_.0'&gt;), '\ufdd0:ambush', '\ufdd0:treasure'],
['\ufdd0:start', '\ufdd0:inn', '\ufdd0:stream', ('\ufdd0:hidden-way' '\ufdd0:forest-clearing' '\ufdd0:grotto' . &lt;'_.0'&gt;), '\ufdd0:forest', '\ufdd0:ambush', '\ufdd0:treasure'],
['\ufdd0:start', '\ufdd0:forest', '\ufdd0:inn', '\ufdd0:stream', ('\ufdd0:hidden-way' '\ufdd0:forest-clearing' '\ufdd0:grotto' . &lt;'_.0'&gt;), '\ufdd0:ambush', '\ufdd0:treasure']]

Now there’s a hidden path that may branch off from the main path. Since we didn’t specify the end, there’s an unbound variable that may have any value (it’s dangerous to wander around, you never know where you end up). For loops and more complex structures, lists probably won’t be enough, but we have to create a new data structure and accompanying functions.

Adderall: appendᵒ, firstᵒ and restᵒ

This time I have been playing around with lists and various relations that are defined with them.

First example is with appendᵒ. This construct is used in conjunction with lists. Essentially “these two lists appended will form the third list”. The example below is used to find all ways of creating list [“a” “b” “c” “d”] with two lists and it will produce 5 different solutions:

(run* [q]
  (fresh (x y)
    (appendᵒ x y ["a" "b" "c" "d"])
    (≡ #t(x y) q)))

[([], ['a', 'b', 'c', 'd']),
(['a'], ['b', 'c', 'd']),
(['a', 'b'], ['c', 'd']),
(['a', 'b', 'c'], ['d']),
(['a', 'b', 'c', 'd'], [])]

Closely related to appendᵒ is firstᵒ and restᵒ. firstᵒ takes the first element of a sequence and restᵒ takes everything else, except the first (so, rest of them, hence the name).

For example, if q is the first element of a sequence and it has value of 1, what possible solutions exists? The answer of course is that there are inifinite amount of solutions, but they can be expressed as [(1 . <‘_.0’>)]. A pair, where first element is 1 and the second element can be anything.

(run* [q]
  (firstᵒ q 1))
[(1 . <'_.0'>)]

Likewise, it is possible to say “if there is a sequence [1 2 3 4] and q is the rest of it, what value q has?” There is only one answer [2 3 4].

(run* [q]
  (restᵒ [1 2 3 4] q))
[[2, 3, 4]]

Now comes something nifty (lifted from http://jrheard.tumblr.com/post/43575891007/explorations-in-clojures-core-logic). Since there is no way to specify the second element of a sequence, we have to write that by ourselves. We could just write required logic every time we needed it, but it is handier to write it as a reusable function:

(defn secondᵒ [l x]
  (fresh [r]
    (restᵒ l r)
    (firstᵒ r x)))

secondᵒ takes two parameters, then it creates a new logical variable as a helper. r is defined to be all but first element of given sequence. x is then defined to be the first element r, which is the second element of l (the original list).

Armed with this new relation, we can revise the original program to consider only answers where first or second element of y is “c”. This effectively limits the possible ansers to two, as shown below:

(run* [q]
  (fresh (x y)
    (appendᵒ x y ["a" "b" "c" "d"])
      (condᵉ
        [(firstᵒ y "c")]
        [(secondᵒ y "c")])
    (≡ #t(x y) q)))

[(['a'], ['b', 'c', 'd']),
(['a', 'b'], ['c', 'd'])]

This isn’t exactly rocket science, but still couple steps further than in the previous post. We know couple more tools more and can create new ones if existing ones aren’t enough.

Adderall: ≡ and consᵒ

My adventures at Hy seas continue and I’m still trying to chart the magical island of Adderall. This time I’m playing around with ≡ (also known as unifyo) and consᵒ (conso to buddies). The ≡ is used to unify two values (more or less saying these two things are same). For example:

(run* [q]
  (≡ 2 q))

This is equivalent of saying “lets say q and 2 are same, now give me all possible values of q”. The answer is of course 2. Not very interesting, but still, this is one of the building blocks.

We can make multiple unifies, like in:

(run 1 [q]
  (fresh (x y z) 
    (≡ x z) 
    (≡ 3 y)
    (≡ [x y z] q)))

fresh is used to introduce three variables x, y and z. After that, we specify that x and z have same value and y and 3 have same value. Last row specifies that [x y z] (a list made of them) and q have same value. Since we’re asking for all possible values of q, we get result as: [[<‘_.0’>, 3, <‘_.0’>]]. y equals three, while x and z can be any value, as long as they are the same value.

Of course, if we have contradicting specifications, results are not found:

(run* [q]
  (≡ 2 q))
  (≡ 3 q))

consᵒ is a bit more complex (but not by much). In lisp, cons is used to form a pair of values and have traditionally been used to make linked lists.

(run* [q]
  (consᵒ 2 3 q))

This is equivalent of saying: “pair made of 2 and 3 is same a q, find me q”. The result is [(2 . 3)]. This is where it gets interesting:

(run* [q]
  (consᵒ 2 q [2 3 4]))

This is same as “making a pair of 2 and q is same as [2 3 4], find me all possible values of q”. The result is [[3, 4]]. So if you take a pair of 3 and 4 and pair that with 2, you’ll get [2, 3, 4]. Pretty nifty?

We can even say:

(run* [q]
  (fresh (x y) 
    (consᵒ x y [2 3 4])
    (≡ [x y] q)))

Which is somewhat like “given we have x and y, and when they are paired together we get [2 3 4]. and [x y] has same value as q. find me all possible values of q”. The result for this is [[2, [3, 4]]] (essentially a list of 2 3 4).

I’m still playing around with very basic relations, but already I can see that there’s very promising possibilities with Adderall (and miniKanren in general). I can take bunch of values, perform an operation to them and get the result. Or, I can have an end goal, bunch of variables and an operation and Adderall tells me how to get there. Or, I can have everything and just have Adderall to check if the result is correct.

Adderall

I have previously written about Adderall and logic programming in general, but I never made a really serious attempt on learning it. I’m going to give it a another go and see how far I get this time. Since I don’t have the Reasoned Schemer (which supposedly is really great book though), I have to rely on resources at http://minikanren.org/. Bear in mind, that I’m still learning all this stuff and most of my explanations might be completely wrong.

With miniKanren, I should be able to define one or more variables and some rules that define their values or relations. Adderall can then work it’s magic and find me missing values or verify that the results I have are correct (this is pretty hazy description, but I’m still trying to grasp the whole thing). It is possible to extend miniKanren (and Adderall I suppose) to work in constraint logic programming, which is the part I’m mainly interested at the moment.

An example program for Adderall is shown here:

(run* [q]
  (condᵉ
    [(≡ true q)]
    [(≡ false q)]))

Essentially, it is asking all possible values of q, when q is true or q is false. Output of the program is [true, false]. ≡ is unification operator and as the name implies, it is used to unify two values. condᵉ on another hand, is used to return multiple values. It can read as or in this case (at least in this case).

This doesn’t look particularly powerful or even useful. But these are just very basic building blocks that are built upon and extended to create more powerful tools. For example, here is a way of solving the zebra puzzle with Adderall.

Adderall

Not too long ago I was playing around with logic programming and thinking if I want to use that in pyherc. In the end I decided against it and one of the reasons was that I didn’t find a library that I liked using (another was that I really didn’t know anything about logic programming). However, just recently a new library was uploaded to PyPi: Adderall. Adderall is a minikanren implementation written in Hy.

I still don’t know much about logic programming, but now at least there’s another library in PyPi to play around with. Adderall is much simpler than pyDatalog that I was trying to use earlier. Maybe that means that it will also be easier to get started with.