It’s been a year since I last wrote about F# and Mono - what’s happened since then?

F# 3.0 has recently been released, bundled with the new all-grey, ALL-CAPS Visual Studio 2012. The biggest new feature is type providers, bringing some of the benefits of dynamic languages into the type-safe world. Innovations like type providers deserve more industry attention. I really hope these ideas will spread and hopefully languages like Scala will pick them up so more developers (including me) can enjoy the benefits.

I’ve written about Datalog and Datomic recently. To conclude, here’s another post comparing execution speed with the contrib.datalog library by Jeffrey Straszheim. Clojure 1.4-ready source can be found here.

The example I’m using in my benchmark is a simple join between two relations. In Datomic/Datalog, it would look like this:

(q '[:find ?first ?height
     :in $a $b
     :where [$a ?last ?first ?email] [$b ?email ?height]]
   [["Doe" "John" "jdoe@example.com"]
    ["Doe" "Jane" "jane@example.com"]]
   [["jane@example.com" 73]
    ["jdoe@example.com" 71]])
;; #<HashSet [["Jane" 73], ["John" 71]]>

In contrib.datalog, the same query requires more ceremony. You can write it like this:

Mr. David Nolen recently published core.logic 0.8.alpha2, with added cKanren (c for constraints) support. To celebrate this glorious event, I’m writing up some core.logic/cKanren stuff I’ve been looking at recently.

Enter the Queens

If you’ve followed this blog, you’ve perhaps seen my previous posts on solving N-Queens in core.logic (part 1 and part 2). How will this look and perform using the new shiny cKanren extensions in core.logic 0.8? Obviously, there are many (new) ways to solve this problem. Here’s a core.logic-styled version of the solution described in the cKanren paper (please read paragraph 4.2 for an in-depth explanation):

Here I present a couple of examples of the functional design pattern “untying the recursive knot.” I’ve found this useful on several occasions, for instance, when breaking apart mutually recursive functions. This material was inspired by Jon Harrop’s excellent Visual F# for Technical Computing.

First, let’s look at a simple factorial implementation using direct recursion:

(defn fact [n]
  (if (= n 0) 1
      (* n (fact (dec n)))))

We can break the direct recursive dependency by replacing the recursive calls with calls to a function argument:

This is a follow-up to my previous post on datalog-equivalent queries in core.logic.

Here I present an alternate way to do the unification and join inside core.logic (without having to use clojure.set/join). It uses the relationships/facts API in core.logic, described here. First, let’s consider this Datomic query:

(q '[:find ?first ?height
     :in [[?last ?first ?email]] [[?email ?height]]]
   [["Doe" "John" "jdoe@example.com"]
    ["Doe" "Jane" "jane@example.com"]]
   [["jane@example.com" 73]
    ["jdoe@example.com" 71]])
;; #<HashSet [["Jane" 73], ["John" 71]]>

In core.logic we start by defining the relationships between our 2 datasets:

I’ve been toying with Datomic recently, and I particularly like the power of its query language (~Datalog). Mr. Halloway showed a couple of months ago how the query engine is generic enough to be run on standard Clojure collections, gist here. Here is an example from that page of a simple join;

(q '[:find ?first ?height
     :in [[?last ?first ?email]] [[?email ?height]]]
   [["Doe" "John" "jdoe@example.com"]
    ["Doe" "Jane" "jane@example.com"]]
   [["jane@example.com" 73]
    ["jdoe@example.com" 71]])
;; #<HashSet [["Jane" 73], ["John" 71]]>

A question you might ask yourself is how can you use core.logic to do the same kind of queries? It turns out that it’s pretty straightforward, and also very fast. Core.logic provides some convenient helper functions for unification that we are going to use. Here’s an example of how to get a binding map for some logical variables over a collection;

This post is a follow-up to my previous post on N Queens and core.logic, in which I tried to find solutions using “pure” logic (without arithmetic goals) and basic miniKanren/Reasoned Schemer building blocks.

After excellent feedback and hints from David Nolen (big thanks), I present a greatly simplified (and faster) way of using core.logic to find all solutions. Credit also goes to good old Bratko.

First, let’s fix the safeo function (and def-subo macro). In miniKanren, you can use arithmetic goals given two prerequisites: the fresh variable must be bound to a finite (number) space, and we must use project to bind the values. This means we can get rid of subo altogether.

I’ve been “hammock-reading” the excellent Reasoned Schemer book these last couple of months, on my quest to develop a gut feel for when logic programming, as defined by miniKanren/core.logic, is applicable.

My first attempt is to apply it to a problem where (as it turns out) miniKanren isn’t a good fit: n-queens. What you really need for this problem in the logical programming world is something called constraint logic programming (CLP), which is implemented (for example) in cKanren. The good people at core.logic are working on integrating CLP and cKanren in core.logic in version 0.8, so I intend to revisit this problem as that work progresses.