Welcome! Please see the About page for a little more info on how this works.

0 votes
in core.logic by

I have a packing problem somewhat adjacent to the "make change" problem described and solved in this blog post by Taylor Wood. Here is the code, transcribed with 1 addition:

(ns blah
  (:require [clojure.core.logic :refer :all :as l]
            [clojure.core.logic.fd :as fd]))

(defn productsumo [vars dens sum]
  (fresh [vhead vtail dhead dtail product run-sum]
     [(emptyo vars) (== sum 0)]
     [(conso vhead vtail vars)
      (conso dhead dtail dens)
      (project [vhead]
        (do (println vhead) succeed))  ;;<--- Just a lame goal that should print out the head..
      (fd/* vhead dhead product)
      (fd/+ product run-sum sum)
      (productsumo vtail dtail run-sum)])))

(defn change [amount denoms]
  (let [dens (sort > denoms)
        vars (repeatedly (count dens) lvar)]
    (run* [q]
      ;; we want a map from denominations to their quantities
      (== q (zipmap dens vars))
      ;; prune problem space...
      ;; every var/quantity must be 0 <= n <= amount
      (everyg #(fd/in % (fd/interval 0 amount)) vars)
      ;; the real work
      (productsumo vars dens amount))))

user> (change 14 #{1 5 10})
({10 0, 5 0, 1 14} {10 1, 5 0, 1 4} {10 0, 5 1, 1 9} {10 0, 5 2, 1 4})

When run, instead of getting the projected or current value of the LVar vhead, as I expect and have normally seen when I use project, I get the Lvar. Are there any ideas why this is the case?

My specific use case is a modification of productsumo, where I have a map of key->weight that I need to use in liue of the coll dens that is here. My initial approach - which seems reasonable - is to use project as above to unify a cost LVar based off the current value of vhead, and then use that in the product computation. Currently I keep getting back LVars instead of values.

Any ideas?

1 Answer

0 votes
selected by
Best answer

the fact that you are getting an lvar out of project means there isn't a "current value of the LVar vhead"

Project is non-relational, what this largely means is it is very order dependent,

for example:

user=> (doall (l/run 1 [q] (l/fresh []  (l/== q 1) (l/project [q] (do (println q) l/succeed)))))
user=> (doall (l/run 1 [q] (l/fresh [] (l/project [q] (do (println q) l/succeed)) (l/== q 1))))

So when you get an lvar instead of the value you expect, it is because the goals that you expect to assign a value to the lvar have not been executed yet.

I don't know what your level of experience is with core.logic/prolog/minikanren, but if are starting out/learning, I recommend forgetting that project exists. It can be a useful hack(for debugging, performance, or for writing interfaces between core.logic and other systems), but if your goal is to write logic programs, it will get in your way.

Thanks for the reply.  I think core.logic support is relatively sparse, happy to get a response.

>what this largely means is it is very order dependent

That makes sense.  However, the goal in the submitted conde expression has conso binding `vhead` prior to the projection; unless I am missing something about goal ordering in conde (they mention something about goals being interleaved).  Unless goal ordering is utterly arbitrary (I don't think so, since we explicitly order goals to optimize queries and prune the search space....).
just because vhead is used in an earlier goal doesn't mean it is ground (has a determined value). The vars seq passed is a sequence of lvars, each constrained to be in a finite domain, but they are not ground, and vhead is unified with the first element of vars (what conso does). so vhead is not ground.

The interleaving is about how core.logic (and minikanren) handle branches in the search tree, and does not effect the order in which goals are run. It is an often sited difference between minikanren and prolog. Prolog effectively does a depth first search, if you have a branch, and the first alternative doesn't terminate (it diverges, has some kind of infinite loop), and the second alternative does terminate in an answer, prolog won't produce the answer because it gets stuck on the first alternative. Minikanran will do a little work on the first alternative, then a little work on the second, then back to the first, etc.