Clojurians Log v2

Some other things on the way that I will follow up with after the interpreter code • fresh which allows for fresh variables in the usual logic programming sense • project which allows for the current state of variables to be queried (actually way cooler than this) Example of fresh:

(m/match [1 2]
  [(m/fresh [?x]
     ?x)
   ?x]
  ?x)
;; => 2

;; (m/project <yield-pattern> <query-pattern> <value-pattern>)
;;
;; Attempts to yield an object described by yield-pattern using the
;; current bindings and match that object with query-pattern. If
;; successful, attempts to match the target object with value-pattern
;; if querying, or yield the object if yielding. Global bindings are
;; not altered when yielding the yield-pattern object.
(m/search 10
  ;; Capture two 10 in !x
  ;;   Bindings: {!x [10 10]}
  ;; Project the vector [!x !x] e.g. [10 10]
  ;; Match against [?x ?y]
  ;;   Bindings: {!x [10 10], ?x 10, ?y 10}
  ;; Match 10 against ?x
  (m/and !x !x (m/project [!x !x] [?x ?y] ?x))
  {:!x !x, :?x ?x, :?y ?y})
;; => ({:!x [10 10], :?x 10, :?y 10})

Both of these will be usable on both sides.

https://clojurians.slack.com/archives/CFFTD7R6Z/p1608062032462800

I’m working on editing the Meander documentation. Can somebody give me more background on the differences between match and find? I understand the difference between match and search, but the only difference between match and findseems to be that I can use some pattern operations like scan in find, but not in match. Is that it? If so, why not just use find everywhere and do away with match? I assume that there is some sort of performance difference between the two, but it isn’t really mentioned. Is there anything else that find can do that match can’t, or vice versa?

Match is unambiguous. We aren’t searching to find a way to satisfy the pattern. We are just matching very directly what was given. Given that we aren’t searching, match does have in general better performance characteristics. Find can do anything match can do. But match can’t use things that require searching to satisfy the pattern. Another way of putting it is that match allows there to only be exactly one match. Find allows there to be more than one, but selects the first.

Also, thanks for any edits you are doing. Always wonderful to have people help out with that 🙂

LOL just backspaced a bunch.

The semantics of find are basically (first (search ,,,)) but compiles to code specifically designed to find the first solution more efficiently.

So, define “searching” in the way that Meander uses the concept. How is what match does not searching while what search/`find` do is searching.

Yes, I get the diff between search and find. Totally makes sense.

It’s the diff between match and find (and search) that has me scratching my head.

match is searching in the traditional sense of pattern matching found in virtually every language that has it. Patterns must be unambiguous and match throws when there is no default and no match; pretty much core.match style.

Both search and find allow for ambiguous patterns and neither complain when there is no solution found.

What does “ambiguous” mean? Just that more than one pattern matches?

OK, good point that neither search or find complain about nothing found. That’s important.

An example of an ambiguous pattern would be {?k ?v} or {?k ?v, ?v ?k} because there is no one solution given a satisfactory map of the right shape.

Hm. So how does it deal with {?k ?v}? What are the variables bound to?

So a map like {:x 1 :y 1} in the first example could bind ?k to either :x or :y.

Got it. So does it just choose one?

The first?

find does, search returns both answers.

find just picks the first one blindly.

Depth first.

OK, make sense. search returns both and find returns whatever search would find first.

Another example would be [_ … ?x . _ …] aka (m/scan ?x). Some ?x is in there.

Right.

But you don’t want to call first on search because and prefer find because find avoids making collections etc.

Or, at least, it tries to avoid them as often as possible.

OK, got it. So basically, match wants things to have a single possibility. search is willing to have multiple possibilities, which it can deal with because it returns all of them. And find is effectively an optimized version of (first (search …)).

Thanks for the help. Another question so another thread. It seems like search (and find) are almost Prolog-like in how they accomplish the search. It seems it’s performing backtracking in some sort of search tree across the whole pattern(s). Is that a good way to think about it?

Does Meander return all results from search in a list instead of a lazy seq? In other words, does one ever have to worry about laziness, or is that a non-issue?

It’s lazy.

So, don’t wrap it in binding 🙂

find and match are, OTOH, eager.

Is it? I see: (class (m/search 1 1 :one)) ;; => clojure.lang.PersistentList

That is probably not reliable.

(let [x {:a 1 :b 2 1 :a :d 4}]
  (class
   (m/search x
     {?k ?v ?v ?k}
     x)))
;; => clojure.lang.LazySeq

Yep: (class (m/search [1 2 3 4] (m/scan ?x) ?x)) ;; => clojure.lang.LazySeq

So, what can we say about the return type? It conforms to sequential? ??

Yeah, I guess. Or that it matches the pattern (_ …).

This the spec

(s/fdef meander.match.epsilon/search
  :args (s/cat :expr any?
               :clauses :meander.match.epsilon.match/clauses)
  :ret (s/coll-of any? :kind sequential?))

Seems like it returns: nil (no match), PersistentList, and LazySeq, depending on the case.

From meander.match.specs.epsilon

OK, so it’s basically a sequential?.

Yeah.

BTW, specs are mostly in these “private” namespaces.

Should it return () for no match, instead of nil?

Yes.

OK, I can take a look at the specs.

(m/search 0 1 :one) ;; => nil

not ()

and (sequential? nil) is false

Ah, well I guess then the spec is wrong. 🙂

LOL. 🙂 I just gave you another unit test.

Eh, no.

But, yeah, sure.

Heh, I’m pretty sure would could figure out why its not a list because, I would actually agree there is merit to it having a () output at minimum.

nil seems fine. And probably best not to change it now.

We can fix the spec though

You want me to file a low priority bug? I don’t know that it would cause a problem very often, but it seems like empty list is better than nil.

Yeah, but it is also a breaking change. Just imagine it in a when

I agree. Yes you can file the ticket but here’s the thing: I really want to stop working on epsilon

Basically, a user should be checking for no result with (empty? (m/search …), right?

Understood. Do you have a way to tag it for zeta?

In fact, I would like to personally stop working on epsilon, take the stuff that I like to zeta, integrate it and start building there.

You can tag it as both.

Because I think it should be fixed.

I agree with your position. 🙂

OK, I’ll file it.

Pointing out these flaws keeps me motivated.

Corner cases. Gotta love ’em. :face_with_rolling_eyes:

Yah.

I’m a product manager for my day job, but I should have been a tester.

Seriously the best way to see commits on the project is to come here and point out a thing or two 😅

Semantics are important!

BTW, did you see my question about Meander search being sort of Prolog like? Did that make sense?

Yes it does. search is basically like unify with a ground term.

Yep

OK, cool. Then it wasn’t my imagination. 🙂

It’s kinda like conde 😎

And scan is something close to member/3 in Prolog.

Right

Lemme check

Not member/2? I just did a quick search and that’s all I see from the SWI docs.

Sorry, yea, member/2.

Yes but it’s more like searching for a subsequence.

(m/scan ?x ?y ?z) ~= [_ ... ?x ?y ?z . _ ...]

Right. It’s the backtracking that got me. So, even if you only have one pattern, you’re doing backtracking within that pattern if you’re using scan.

Or rather particular elements of a subsequence.

Yep.

And you’re calling the expression every time. Backtracking. Rebinding logic vars. Then calling the expression. And so on.

Of course, we try to find the best way to create the smallest search space to minimize that by exploiting what we know.

BTW, I found something else while I was cooking up more examples for the docs.

Yes, but again, we try to minimize that.

Share away

(m/search {:a [1 2] :z [:x :y]} {:a (m/scan ?a) :z (m/scan ?z)} [?a ?z]) ;; => ([1 :x] [1 :y] [2 :x] [2 :y]) (m/search {:a [1 2] :b 2 :c 3 :d 4 :e 5 :f 6 :g 7 :h 8 :i 9 :j 10 :z [:x :y]} {:a (m/scan ?a) :b 2 :c 3 :d 4 :e 5 :f 6 :g 7 :h 8 :i 9 :j 10 :z (m/scan ?z)} [?a ?z]) ;; => ([1 :x] [2 :x] [1 :y] [2 :y])

Yes

Both patterns are looking for all possible combinations of ?a in [1 2] at :a and ?z in [:x :y] at :z.

Depending on the number of items in a map literal, Clojure will either put them in a PersistentArrayMap or a PersistentHashMap. If it chooses an array map, then the order is as the user writes them. If hash map, then it’s whatever the hash order is.

And there is no way around that unfortunately.

That changes the order that Meander does the search and changes the order of the output.

It’s not a problem.

It can, yes,

However, I have been thinking that is actually biased.

I just point that out in the (new) docs as something to be aware of.

It will affect find, for instance.

We have ticket for the problem

No solution yet.

Oh, you already have a ticket. Cool. No worries then.

But I’ve been thinking a way to solve it would be to have a method of being able to tell the interpreter/compiler how to produce the space.

Most of the time it shouldn’t matter. And as long as it’s documented, I think it should be OK. I added a short section to the docs that shows the issue and basically says “Don’t rely on the ordering.”

I gotta run and get dinner on the table for my kids. TTYL. Thanks for the help. That was great. I’ll file the bug shortly and I’ll submit a PR with doc updates in a bit.

@droberts3 Thank you 🙏

Good point @jimmy!