Fork me on GitHub
#meander
<
2020-08-25
>
yuhan05:08:02

I haven't used Meander for a while now (deemed too experimental for work use), but wouldn't the "unspecified keys" proposal conflict with the use of ?logic vars as lookup keys in a map?

yuhan05:08:59

(let [db {:user-db {"Alice" {:id 123}
                    "Bob"   {:id 124}}
          :info-db {122 {:favorite-food "nachos"}
                    123 {:favorite-food "noodles"}
                    124 {:favorite-food "nutella"}}}]
  (m/match db
    ;; query: what is Alice's favorite food?
    {:user-db {"Alice" {:id ?id}}
     :info-db {?id {:favorite-food ?food}}}
    ?food))
;; => "noodles"

yuhan05:08:30

can't construct a version with !memory vars at the moment, but it sounds bad for the semantics to be different depending of the type of var

👍 3
noprompt15:08:35

> deemed too experimental for work use Ha! 🙂

nlessa22:08:06

I have being using Meander extensively in production systems and I am very happy with it.

🙂 6
🎉 3
noprompt15:08:35

I see ticket #130 more or less as an invitation to think about how we can improve the visual parts of map/set patterns for the reasons mentioned in that ticket.

noprompt15:08:44

One thing we could do is provide a way to hook into the parser via protocols.

noprompt15:08:57

Clojure doesn’t respect the namespace aliases of tagged literals though which makes doing something like

#my.custom.MapPattern {!k !v}
really gnarly.

noprompt16:08:17

The other possibility is making syntax extensions a bit more interesting.

noprompt16:08:53

There’s also the road of flags.

timothypratley16:08:27

FWIW I’d happily accept the different behavior based on type of var to regain the structure of my expressions 🙂 I have tried to think of ways to explicitly differentiate and unfortunately they all bloat the structure a lot. I really do think it boils down to treating memory variables differently in maps and sets… and that there is significant value in doing so.

noprompt16:08:41

I think there is significant value in achieving what you’re after in #130, however, the culprit is the search space the container represents not the variable.

noprompt16:08:35

I think it has been mentioned before but would you agree with

{& ([!k !v] ...)}
on the match side as a compromise for the moment pending further investigation?

timothypratley16:08:55

I’d rather just stick with map-of or {& (m/sequable than make that change!!! 😛 FWIW I think that violates the structure rules

timothypratley16:08:17

Can you explain more what “the culprit is the search space the container represents not the variable” means?

timothypratley16:08:08

Maybe an example 🙂

timothypratley16:08:26

I think you mean… what is does this mean? {:a 1, !k !v} To which I say it should logically match {:a 1, :c 3} and that !k should be bound as [:a :c] order is arbitrary but matches !v [1 3]

timothypratley16:08:17

Notably if you wanted to you can also write {:a 1, & {!k !v}} and instead have !k/!v only match the remaining map conveniently

noprompt16:08:07

{p1 p2}
represents a submap of the match target of 1 entry. The entry has a key that matches p1 , and value that matches p2. The search space is all of the values which can be yield from the target which have the potential to match. So if the target were
{:a 1 :b 2}
the search space would be
([:a 1] [:b 2])
where one element in the space matches :a and 1 against p1 and p2 respectively, and :b and 2 against p1 and p2 respectively.

noprompt16:08:40

The search space for a map is actually a bit more complex than this but I’m choosing the simplest case for illustration.

noprompt16:08:43

Why is this important? Well if you want the variables to bind differently, you need to change the search space or change the pattern.

noprompt17:08:48

The syntax extensions exist to change patterns which can affect how search spaces are yield.

noprompt17:08:03

However, visually they are not satisfactory.

noprompt17:08:33

We don’t have complete control over how to view a structure in a given context beyond wrapping it in a (symbol p) kind of pattern where symbol has been defined as a syntax extension.

noprompt17:08:07

What would be nice is to be able to say something like

(notation {!k !v} (m/map-of !k !v))

noprompt17:08:46

So instead of making the interpretation of an arbitrary pattern context sensitive with respect to the container it happens to appear in you say instead that here we say that a pattern which looks like this should be replace with a pattern that looks like this.

noprompt17:08:27

So, for this example, you could write

{:a 1 & {!keys !vals}}
and have it expand to
{:a 1 & (map/of !keys !vals)}

yuhan17:08:18

@noprompt that sounds like a pretty dangerous proposal..! I wouldn't trust myself with such large amount of control over the semantics of an expression

👍 3
yuhan17:08:27

currently I can look up where each Meander operator is defined and what it does, with arbitrary notation transforms I won't even be able to tell at a glance what's being transformed and where it's defined

👍 3
timothypratley17:08:01

I’m not really able to follow the “search space” argument; maybe you can simplify for me … observing that maps are sets of key-values … lets just talk about sets, and not use any pre-existing variables like ?k or !k: let’s just talk about #{-k} a magical new thing that will allow me to match a set and substitute its values, is this impossible for some reason? I’m explicitly not including find in this description.

yuhan17:08:48

so this -k is bound to all the values in the set?

timothypratley17:08:26

I’m trying to be abstract and just specify that I’d like

(m/rewrite #{1 2 3}
  #{-k}
  #{-k})
;;=> #{1 2 3}
as a user feature 🙂 I do think that means -k gets bound to all values in the set, which implies why not just do:
(m/rewrite #{1 2 3}
  (m/and #{} ?xs)
  ?xs)
So I need a slightly more motivating example 🙂

timothypratley17:08:55

(m/rewrite #{1 2 3}
  #{-k}
  #{(m/app inc -k)})
;;=> #{2 3 4}

timothypratley17:08:36

I know what you are going to say… oh but -k could have matched any element! Greed is evil! To which I reply this is why I need greed.

noprompt17:08:59

Greed is certainly not evil.

noprompt17:08:45

What is evil is a that a pattern could have different semantics in different contexts: precisely your point about {& ([!k !v] …)} .

timothypratley17:08:55

can you give an example of how #{-k} would have different meanings?

noprompt17:08:05

No because it only has one meaning.

timothypratley17:08:35

I’m so confused 😕 sorry if I’m dense

noprompt17:08:46

The search space yielded by the container determines what values it’s contents will be matched against.

noprompt17:08:55

Tim, you are not dense. 🙂

noprompt17:08:33

I’ve known you for, what, something like 6 years or something? Dense isn’t even on the map. ❤️

timothypratley17:08:00

Is it that #{?k} and #{-k} have different meanings and that’s bad?

noprompt17:08:09

And, fwiw, these conversations are really important.

noprompt17:08:39

It is that, in general, for all patterns p the semantics of #{p} do not change.

timothypratley20:08:06

actually I think this is already broken: #{^& ?rest}

noprompt20:08:51

(let [s #{1 2 3}]
  (m/match s
    #{^& ?rest}
    ?rest))
;; => #{1 3 2}

(let [s #{1 2 3}]
  (m/find s
    #{^& ?rest}
    ?rest))
;; => #{1 3 2}

(let [s #{1 2 3}]
  (m/search s
    #{^& ?rest}
    ?rest))
;; => (#{1 3 2})

(let [s #{1 2 3}]
  (m/rewrite s
    #{^& ?rest}
    #{4 5 6 ^& ?rest}))
;; => #{1 4 6 3 2 5}

timothypratley04:08:18

Ah right, I meant that the notion that for all patterns p the semantics do not change …. #{^& ?rest} is arguably already breaking that (in an expected way) or is it ok because the metadata makes it different? In which case is #{^… !k} ok? Is {^... !k !v} ok?

timothypratley04:08:14

I kinda like {^… !k !v} to be honest… o_O

noprompt17:08:54

This is why I was lamenting the fact that tagged literals could be so bulky.

timothypratley17:08:22

^-k #{} <-- is this ok?

noprompt18:08:32

At the moment, no, BUT the plan is to allow for custom binding semantics. I have a gist where I’ve been playing with this. So when -k binds you could have the definition

(fn [current value]
  (if (seqable? value)
    (into current value)
    UNBOUND))
where current is assumed to be a vector, and UNBOUND represents binding failure.

noprompt18:08:40

So in this way you could say something like

#{^:as -k}

noprompt17:08:41

But I wouldn’t want to get in the way of something like #mine #{!k} where perhaps #mine maps to

(defn mine [value]
  (reify
    m.protocols/IExpandSyntax
    (-expand-syntax [this]
      ,,,)))

noprompt18:08:32
replied to a thread:`^-k #{}` <-- is this ok?

At the moment, no, BUT the plan is to allow for custom binding semantics. I have a gist where I’ve been playing with this. So when -k binds you could have the definition

(fn [current value]
  (if (seqable? value)
    (into current value)
    UNBOUND))
where current is assumed to be a vector, and UNBOUND represents binding failure.

noprompt18:08:40
replied to a thread:`^-k #{}` <-- is this ok?

So in this way you could say something like

#{^:as -k}

timothypratley18:08:48

is here a more direct solution here where I write my own custom tag that translates {!k !v} to (map-of !k !v) and stop complaining?

noprompt18:08:53

That would be the notation idea. I’ve been on the fence about it because, like @qythium pointed out, it’s crazy powerful and could be bad. That being said @jimmy has somewhat convinced me that isn’t necessarily a good reason to dismiss the idea on the grounds that we can’t stop people from obfuscation. defsyntax can easily obfuscate. Going the route of notation should involve a commitment to tooling that enables makes it easier to expand patterns as you would a macro.

timothypratley20:08:56

I’m not sure notation is needed at all… as a user I can write a macro that translates my patterns

timothypratley20:08:36

I mean maybe it solves some other problem 🙂

timothypratley20:08:38

and that’s great.

jimmy20:08:49

We could also expose an ast transformation level if we really wanted to. Not saying we should, but it would solve the problem and also let us experiment with optimizations in an extendable way.

yuhan18:08:06

yeah, the last time I played around with defsyntax I found myself really wishing for a way to macroexpand sub-patterns

yuhan18:08:17

not sure if that's already possible or meaningful

noprompt18:08:38

It is meaningful.

yuhan18:08:17

that's a relief to hear!

yuhan18:08:18

One really nice property I like about Meander is that all the special vars and things are drop-in replacements for literal matches

yuhan18:08:43

there's probably a better way of putting this but it makes a lot of sense in a easy refactoring / referential transparency mindset

yuhan18:08:06

so having !k !v be context dependent would complect the whole situation IMO

noprompt18:08:23

Currently, I’m a huge bottle neck with respect to the project. I’ve got work related requirements and my kids at home 24/7 (two of which are being home schooled now). What I really want to figure out is how to get others involved in a maximally collaborative but minimally pressured way.

noprompt18:08:19

I have a model for zeta that I think is mostly sound in terms of the primitives and assumptions. The interpreted model has explainability built in like spec and it works both for matching and substitution. But I need others to think about it too.

noprompt18:08:17

Compilation can be built on top of that model which can fall back to run time interpretation if needed.

noprompt18:08:54

(let [?x (logic-cell)
      x-> (lifo-cell)
      x<- (fifo-cell)
      pattern (pair (&& (in [1 2 3]) x<- x->)
                    (&& (in [4 5 6]) x<- x->))
      extract-bindings (fn [result]
                         (let [bindings (get result :bindings-out)]
                           {'x-> (get bindings x->)
                            'x<- (get bindings x<-)}))]
  [;; Query the pair [2 6] against the pattern and pull out the
   ;; passing bindings.
   (map extract-bindings
        (filter pass? (query pattern [2 6] {})))
   ;; Attempt to generate 20 solutions and pull out the passing value
   ;; and binding.s
   (map (juxt :value extract-bindings)
        (filter pass? (take 30 (yield pattern {}))))])
;; =>
#_
[({x-> (6 2), x<- [2 6]})
 ([[1 4] {x-> (4 1), x<- [1 4]}]
  [[1 5] {x-> (5 1), x<- [1 5]}]
  [[1 6] {x-> (6 1), x<- [1 6]}]
  [[2 4] {x-> (4 2), x<- [2 4]}]
  [[2 5] {x-> (5 2), x<- [2 5]}]
  [[2 6] {x-> (6 2), x<- [2 6]}])]

noprompt18:08:07

“Two” is what I call the underlying framework. It thinks of variables similar to how Clojure thinks of them in that names point to things but the things are cells which specify how their content is accumulated (fold) and it is dispersed (unfolded).

noprompt18:08:13

At a more general level, patterns of which variables are subset, are objects which define what it means to be queried and also what it means for them to yield their instances.

noprompt18:08:04

IOW, patterns represent elements of sets.

noprompt18:08:56

query asks if a value is a member of those sets and produces bindings. yield asks if a value can be produced given bindings and if so produce those values.

noprompt18:08:04

This is deliberately not unification.

timothypratley18:08:32

@qythium  could you expand on what “all the special vars and things are drop-in replacements for literal matches” means?

yuhan18:08:36

I think of the "base case" for patterns as matching on a pattern made entirely of literals

(m/match [1 2 [3]] [1 2 [3]] :ok)
Then you can iteratively replace subexpressions of the pattern with more complicated concepts like logic vars
(m/match [1 2 [3]] [1 2 ?x] ?x)
knowing that the spot where the ?x goes "resolves" to what could be a base pattern

yuhan19:08:38

I don't know if that's always true eg. cata seems to be context dependent, but I find it a useful mental model

noprompt19:08:11

cata isn’t context sensitive in the sense that its semantics are the same wherever it appears. It is context sensitive in the sense of what the target value is recursively matched against in terms of the system it appears within.

yuhan19:08:38

@noprompt That was quite a bit to digest but really interesting! So fifo-cells are Meander's memory variables?

noprompt19:08:31

Yep. I didn’t chuck in the use of ?x there but it works as you’d expect.

noprompt19:08:55

Keep in mind this is a model for interpretation. This means, at a minimum, we have a non-macro version of search/yield.

noprompt19:08:55

There is some other interesting stuff going on in there too if you’ll notice the use of SplittableRandom and seed.

noprompt19:08:53

The idea here is not only to allow for concepts of matching elements from infinite sets but also producing them.

noprompt19:08:04

This is interesting for something like (sum ?x 3) where the query means find all ?x + 3 = TARGET and yield means all values that give you a value which can match ?x + 3 and, if you want, the bindings that makes that true.

noprompt19:08:54

The streams of data produced by the way include failures unlike previous versions.

noprompt19:08:27

This means that it’s possible to have a model that allows one to explain failures in either case, and, importantly, prevent divergence.

noprompt19:08:28

There’s also a rough sketch of group-by-cell in there.

yuhan19:08:16

This sounds a lot like unification, from the vague familiarity I have with both areas

yuhan19:08:01

ah scratch that, my thinking is too muddled for that to be a coherent question

yuhan19:08:41

I'd love to dive into this in my spare time too and contribute! It's just a little daunting how high-level the concepts seem to be from scanning through the Meander codebase

yuhan19:08:31

Also just throwing out a random thought I had before - seeing as how Meander's vars use different sigils that are compiled into some underlying representation, could this be made into an extendable notation?

noprompt19:08:41

I need write down what I wrote down here on that file, eh? 🙂

💯 3
noprompt19:08:15

I think the sigils are valuable for the macro version for at least things like logic variables.

yuhan19:08:18

(defsigil © 
  "docstring" 
  [sym <other necessary args>] 
  <implementation, compiler/interpreter hooks etc.>) 
where the sigil symbols have to come from the corresponding Unicode punctuation/symbol blocks like Haskell operators

yuhan19:08:43

then you can go around using ©x in patterns with your own user defined semantics

noprompt19:08:54

Yeah. This is something I’ve been thinking about also.

noprompt19:08:40

I think the smallest thing would be declaring variables somehow

(m/declare [$x ([m/unbound 0] 0 _ m/unbound)]
  ,,,)
you get the idea.

noprompt19:08:26

Or maybe [$x ~rewrite-rules] to keep plain functions in the mix.

noprompt19:08:17

Damn you covid-19!

noprompt19:08:32

Oh, before I forget, I should plug #asami as a project to keep an eye on. 🙂

👀 3
noprompt19:08:03

I am on the same team as the original author and am gradually becoming a contributor.

timothypratley20:08:50

I’m really looking forward to the logic-cell stuff as it sounds like a general solution for aggregation/reduce!

timothypratley20:08:01

I’ve attached the “macro solution” of replacing {!k !v} with {& (map-of !k !v)} to issue #130 based on the suggestions here mainly to record it… I can go ahead and start using the macro in my projects and learn the hard way where it will bite me later.

😂 3
nlessa22:08:06

I have being using Meander extensively in production systems and I am very happy with it.

🙂 6
🎉 3