Object Commando languages, development and design

13Oct/114

Appendo the Great

I have been spending a some time recently trying to get a better understanding of logic programming. I was very much inspired by David Nolen's core.logic library. I am reading several different papers and books trying to understand the paradigm. All of them talked about an append function, but I was having difficulty understanding why it was so important.

From the Reasoned Schemer, conso, the relational form of cons, gets the title conso the magnificent. And conso certainly is magnificent, but I think appendo should get some credit too. In core.logic and miniKanren, append is called appendo. Like concat in Clojure it appends two lists together to create a third list. It can be used as a building block for many other functions. The definition of the function (from core.logic) is pretty small:

(defne appendo [x y z]
  ([() _ y])
  ([[?a . ?d] _ [?a . ?r]] (appendo ?d y ?r)))

defne above is syntax sugar around matche. It creates a function (named appendo) that accepts three arguments. It matches x, y and z with the three arguments in the list at the beginning of each clause. In this case the first clause is matched cons style. ?a is declared as the first item and ?d is declared as the rest. The second item is ignored, the third is split in the same way. Note that the ?a is shared here on the first and third parameter of the match. This makes the first item in x, the first item in z. Assuming the x and z can be matched as above, appendo is recursively called on the rest of each list (including y, untouched). Something similar to the shared ?a is going on when the recursion bottoms out (when x is empty). In this clause y is declared as z. This makes y the tail of a cons like expression (specifically the ?r) from the previous recursive call. That's a lot packed into such a small amount of code! Below I will build the case for appendo's new title.

Building Blocks

To run the below code, you need to use the right namespaces. Something like this:

(ns logic-examples.seq
  (:refer-clojure :exclude [inc reify ==])
  (:use [clojure.core.logic minikanren prelude nonrel match disequality]))

I thought I understood the appendo function, but I didn't understand why each source spent a lot of time on it. It seemed straight-forward enough. Then I had that ah-ha moment while reading up on Prolog's prefix and suffix functions. Here's something roughly equivalent in core.logic that I wrote before my ah-ha:

(defne prefixo [x y]
  ([[] _])
  ([[?a . ?xs] [?a . ?ys]] (prefixo ?xs ?ys)))

This declares that x is a prefix of y. So it could be used to delcare an x as [1 2] and y as [1 2 3 4 5]. Like above, it uses defne, matching in a similar way. I'm using the shared ?a? to ensure the first item of x is the first item of y and continue recursively. I then began to think of appendo as less like concat in Clojure and more like what list could I concat with this other list to yield some result list (user specified or not). That realization led me to change my prefixo function to be the following:

  (defn prefixo2 [x y]
    (fresh [a]
           (appendo x a y)))

This function appends x with a new (or fresh) variable to yield the value y. So substituting values into the appendo call (using the above example): (appendo [1 2 3] a [1 2 3 4 5]). When unified, a is obviously [4 5] because appending [1 2 3] with [4 5] would satisfy the result list [1 2 3 4 5]. With some great core.logic magic, a will match anything that would appear after items in x in order to satisfy y. Part of the mind-bending nature of logic programming is the mixture of declaring, binding, predicates and the wiggle room that result variable gives you. As an example, there's no need to provide a defined y in the above call:

(run* [q]
  (prefixo2 [1 2 3] q))
= > ((1 2 3 . _.0))

This code runs prefixo but leaves y fresh. This lets core.logic decide what the value should be. So it is asking what will satisfy prefixo2 when x is [1 2 3]. The answer from core.logic is (1 2 3 . _.0). ._0 is the tail of the list and could represent anything, meaning that y could be a list with 1, 2, 3 followed by nothing or 4 or ["Klaatu" "Barada" "Nikto"]. These arbitrary values are numbered to distinguish between different values in the case that there could be multiple arbitrary values that could be (but don't have to be) different. More examples of _.0 are below. The above code will also handle other constraints on the list:

(defn lasto
  "Declares x as the last item in y"
  [x y]
  (fresh [a]
         (appendo a [x] y)))

(run 3 [q]
  (lasto "Hail to the king baby" q)
  (prefixo2 [1 2 3] q))
= > ((1 2 3 "Hail to the king baby")
        (1 2 3 _.0 "Hail to the king baby")
        (1 2 3 _.0 _.1 "Hail to the king baby"))

This basically says give me three lists where 1, 2, 3 is the prefix and the last element is "Hail to the king baby". A proper [ Army of Darkness ending. The easiest one is the list containing only those four items, which is the first returned. The next solution says any one element can exist between 3 and "Hail to the king baby". The next solution says any two elements can be between the theird and the last elements etc. Passing 3 to run tells core.logic how many solutions you want it to come up with. Using run* will ask for all solutions (not a good idea with this example code). This code has two fresh variables _.0 and _.1. These could be any value. They could be different values or they could both be the number 42. They are labeled distinctly because they could have distinct values.

More appendo fun

Seeing what I could do with prefix, I then followed that with suffix:

(defn suffixo
  "Declares the elements of x as the end of list y"
  [x y]
  (fresh [a]
         (appendo a x y)))

Nothing new there. membero is a function in core.logic that declares that x (an element) occurs in a list y. A version can also be built out of appendo (though probably not as efficiently):

(defn my-membero
  "A (probably inefficient) function stating x is an element in y"
  [x y]
  (fresh [a b]
         (appendo a (llist x b) y)))         

(run* [q]
     (my-membero q [1 2 3 4 5]))
= > (1 2 3 4 5)

(run 5 [q]
  (my-membero 3 q))
= > ((3 . _.0) (_.0 3 . _.1) (_.0 _.1 3 . _.2) (_.0 _.1 _.2 3 . _.3) (_.0 _.1 _.2 _.3 3 . _.4))

The first example of it's use gives a list of [1 2 3 4 5] and asks core.logic to come up with all of the members (which is just each element). The second asks the opposite question. Declaring that 3 is in the list, what are the lists that would satisfy it. The first result has 3 as the first element (followed by anything), the second list has 3 as the second element (followed by anything) and so on.

Using appendo to find sublists was interesting:

(defn sublisto
  "The list x (in sequence) appears in y"
  [x y]
  (fresh [a b c]
         (appendo a b y)
         (appendo x c b)))

= > (set (run* [q]
        (sublisto q [1 2 3 4 5])))
= > #{() (1) (2) (1 2 3) (2 3) (3) (3 4) (4 5) (2 3 4) (1 2 3 4 5) (1 2) (2 3 4 5) (4) (3 4 5) (1 2 3 4) (5)}

Chaining it together with my-membero can find all sublists containing a particular number:

(set (run* [q]
       (sublisto q [1 2 3 4 5])
       (my-membero 2 q)))
= > #{(2) (1 2 3) (2 3) (2 3 4) (1 2 3 4 5) (1 2) (2 3 4 5) (1 2 3 4)}

Or with the help of adjacent, we can find all sublists where two numbers occur next to each other:

(defn adjacent
  "Declares x and y as adjacent items in list z"
  [x y z]
  (fresh [a b]
    (appendo a (llist x y b) z)))

(set (run* [q]
       (sublisto q (apply concat (repeat 2 [1 2 3 4 5])))
       (adjacent 5 1 q)))         

= > #{(1 2 3 4 5 1 2 3) (4 5 1 2 3) (3 4 5 1 2 3 4 5) ...}

This will only find sublists that have x followed by y, and it must be in that order. To make adjacent a little more flexible, the below version will find x and y next to each other, regardless of order:

(defn adjacent
  "Declares x and y as adjacent items in list z"
  [x y z]
  (fresh [a b]
         (conde
          ((appendo a (llist x y b) z))
          ((appendo a (llist y x b) z)))))

(set (run* [q]
       (sublisto q (apply concat (repeat 2 [1 2 3 4 5])))
       (adjacent 5 1 q)))         

= > #{(1 2 3 4 5 1 2 3) (4 5 1 2 3) (3 4 5 1 2 3 4 5) ...}

(set (run* [q]
       (sublisto q (apply concat (repeat 2 [1 2 3 4 5])))
       (adjacent 1 5 q)))

= > #{(1 2 3 4 5 1 2 3) (4 5 1 2 3) (3 4 5 1 2 3 4 5) ...}

(= (set (run* [q]
          (sublisto q (apply concat (repeat 2 [1 2 3 4 5])))
          (adjacent 5 1 q)))
   (set (run* [q]
          (sublisto q (apply concat (repeat 2 [1 2 3 4 5])))
          (adjacent 1 5 q))))

= > true

That's a lot of power from a little function. I think appendo deserves the title. The code for the functions above can also be found here.

Comments (4) Trackbacks (0)
  1. lot’s of spanish mumbo jumbo

  2. (defn adjacent
    “Declares x and y as adjacent items in list z”
    [x y z]
    (fresh [a b]
    (appendo a (llist x y b) z)))

    (set (run* [q]
    (sublisto q (apply concat (repeat 2 [1 2 3 4 5])))
    (adjacent 1 5 q)))

    = > #{(1 2 3 4 5 1 2 3) (4 5 1 2 3) (3 4 5 1 2 3 4 5) …}

    Should be

    = > #{}

    because there is never a 1 followed by a 5 in any sublist.

    Thanks for this great article.

    Juan Manuel

  3. Nice catch! I updated adjacent to not care about order out on github, but forgot to paste the new one into the blog post. Thanks for letting me know, should be correct now.

  4. Sorry it took me so long to read this.

    I picked up on an issue with adjacent myself. I think in the process of updating it, you missed what you had been originally trying to say.

    Right now, both versions of adjacent are identical. Juan is correct in pointing out that by looking (1 5) wouldn’t find anything, but you should have left it as it was, and just asked for (5 1) instead.

    (defn adjacent
    “Declares x and y as adjacent items in list z”
    [x y z]
    (fresh [a b]
    (appendo a (llist x y b) z)))

    (set (run* [q]
    (sublisto q (apply concat (repeat 2 [1 2 3 4 5])))
    (adjacent 5 1 q)))

    Of course, the second version, where you look for xy and then yx is just fine.

    I enjoyed it too, thanks.


Leave a comment

(required)

No trackbacks yet.