Clojurians Log v2

@timothypratley Here’s an equivalent example just using meander.epsilon/search.

(m/search (fetch-as-hiccup company-directory-page)
  (m/$ [:div {:class "directory-tables"}
        . _ ...
        [:h3 _ ?department & _]
        _
        [:table &
         (m/$ [:tbody & 
               (m/scan [:tr
                        . _ ...
                        [:td {} & (m/scan [:a {} ?name & _])]
                        _ 
                        [:td {} ?title & _]
                        _
                        [:td {} _ [:a {:href ?mailto} & _] & _]
                        & _])])]
        & _])
  {:department ?department
   :name ?name
   :title ?title
   :email (subs ?mailto 7)})

oh wow, nice!!!

I noticed in the source code for epsilon there is a sibling syntax to $ called $* what does that do?

If memory serves, the context argument is a function so you can apply the function to the context. But honestly not 100% sure

I took a shot at creating my own syntax for “find these things in order ignoring before, between and after”

And along the way I got confused by this behavior:

(m/search [:a [1 "a"] :b [2 "b"] :c [3 "c"] :d]
          (m/scan [1 ?a] :b [2 ?b] :c [3 ?c])
          [?a ?b ?c])
;;=> (["a" "b" "c"])

But then:

(m/defsyntax scan'
  [& patterns]
  (case (:meander.syntax.epsilon/phase &env)
    :meander/match
    (clojure.core/let [inner `(~@'(_ ...) ~@patterns ~@'(. _ ...))]
      `(seqable ~@inner))

    ;; else
    &form))

(m/search [:a [1 "a"] :b [2 "b"] :c [3 "c"] :d]
          (scan' [1 ?a] :b [2 ?b] :c [3 ?c])
          [?a ?b ?c])
=> nil

I know the syntax is being called because I added prn debugging

Oh gosh ignore all that, it should be m/seqable<-- didn’t realize that was a syntax

[meander/epsilon "0.0.340"]

Thanks @timothypratley and @jimmy! 👍

So here’s my implementation:

(m/defsyntax scan*
  "Match patterns in order ignoring things around and between them.
  _ ... p1 . _ ... p2 . _ ... ,,, pn . _ ...
  where `p1` through `pn` are `patterns`."
  [& patterns]
  (m/rewrite patterns
             ;; convert patterns to memory variables
             (!pattern ...)
             ;; substitute patterns interspersed with ignore anything
             (`m/seqable .
              '_ '... !pattern '. ...
              '_ '...)))

@timothypratley There’s something like that currently called separated.

but it produces: => ([“a” “b” “c”] [“a” “b” “c”] [“a” “b” “c”] [“a” “b” “c”])

https://github.com/noprompt/meander/blob/epsilon/src/meander/epsilon.clj#L355

(meander.epsilon/seqable _ ... [1 ?a] . _ ... [2 ?b] . _ ... [3 ?c] . _ ...)

oh right…

;; Prevent producing the same search results twice when ;; the target is a vector. Sounds relevant…

I think the implementation could simply rely on seqable when the problem I mentioned about or in the seqable implementation goes away.

Hmmm same problem:

(m/search [:a [1 "a"] :b [2 "b"] :c [3 "c"] :d]
          (m/separated [1 ?a] [2 ?b] [3 ?c])
          [?a ?b ?c])
=> (["a" "b" "c"] ["a" "b" "c"] ["a" "b" "c"] ["a" "b" "c"])

The output sould be (["a" "b" "c"]) as there is only one way to match the pattern

Not exactly.

Well, hmm…

Yeah, thats probably a bug.

(m/search [1 2 3 4 5]
          [1 . _ ... 2 . _ ... ?x & _]
          ?x)

^^ this seems like a good example without any syntax stuff

want me to open an issue?

Yeah that makes sense though because the width of the last _ … grows to the point where the & _ ends up nothing.

(m/search [1 2 3 4 5]
  [1 . _ ... 2 . _ ... ?x & ?rest]
  [?x ?rest])
;; =>
([3 [4 5]] [4 [5]] [5 []] [4 [5]] [5 []] [5 []])

the answer should be (3 4 5) surely?

And, yes, do open an issue on that

(m/search [1 2 3 4 5]
  [1 . _ ... 2 . !part-a ... ?x . !part-b ...]
  {:part-a !part-a
   :x ?x
   :part-b !part-b})
;; =>
({:part-a [], :x 3, :part-b [4 5]}
 {:part-a [3], :x 4, :part-b [5]}
 {:part-a [3 4], :x 5, :part-b []})

So the bug seems to be with _ …

yeah it probably treats them all the same

Yeah, they’re called “drops” :drp nodes and there’s some handling for patterns that use a lot of them. I can take a look at it tomorrow.

(m/search [1 2 3 4 5]
          [1 . !a ... 2 . !b ... ?x . !c ...]
          ?x)
=> (3 4 5)

Yeah.

Okay, open a ticket for that.

I can’t look at it tonight unfortunately.

:thumbsup: will do!

yeah no rush at all man

But it probably has something do with the final case of :prt in match namespace that handles variable length on both sides.

There’s a function in the syntax namespace called window and a couple other that are connected to it.

Probably something off in there.

Thanks for flagging these!

I did a fair bit of pushing myself during the Clojurist Together sprint and made some mistakes along the way. 🙂

Just gotta get them ironed out now! 😄

My pleasure! Hahaha well I’m really liking the new stuff 🙂

Cool! I’m glad.

https://github.com/noprompt/meander/issues/74

☝️ I think we might want to roll in map-of / set-of soonish.

Chime in if you have any thoughts on that one.

Oh lol, hear me out on one thing!!!

(m/search [1 2 3 4 5]
          [1 . !_ ... 2 . !_ ... ?x . !_ ...]
          ?x)

^^ this produces the right result

hahahaha well it doesn’t really solve anything

it was just interesting

(m/search (fetch-as-hiccup company-directory-page)
             ;; match
             (m/$ [:div {:class "directory-tables"} &
                   (m/scan
                    ;; match heading/table pairs
                    [:h3 {} ?department & _]
                    _
                    [:table &
                     (m/scan
                      [:tbody &
                       (m/scan [:tr &
                                (separated
                                 [:td & (m/scan [:a {} ?name & _])]
                                 [:td {} ?title & _]
                                 [:td & (m/scan [:a {:href ?mailto} & _])])])])])])
             ;;=>
             {:department ?department
              :name ?name
              :title ?title
              :email (subs ?mailto 7)})

(m/defsyntax separated
  "Match patterns in order ignoring things around and between them.
  _ ... p1 . _ ... p2 . _ ... ,,, pn . _ ...
  where `p1` through `pn` are `patterns`."
  [& patterns]
  (m/rewrite patterns
             ;; convert patterns to memory variables
             (!pattern ...)
             ;; substitute patterns interspersed with ignore anything
             (`m/seqable .
              '!_ '... !pattern '. ...
              '!_ '...)))

How would I bind a variable on the LHS to an expression dependent on a sub-pattern?

I got there with let and a single logic variable, but can't figure out how to do it for a sequence

(m/match 10
  (m/and ?num
    (m/let [?parity (if (even? ?num) :even :odd)]))
  [?num ?parity])
;; => [10 :even]

(m/match [0 1 2 5 8]
  [(m/and !num
     (m/let [!parity ??]))
   ...]
  [!num !parity])

Does this help?

(m/search [0 1 2 5 8]
          (m/scan (m/and ?num (m/let [?parity (if (even? ?num) :even :odd)])))
          [?num ?parity])
=> ([0 :even] [1 :odd] [2 :even] [5 :odd] [8 :even])

hmm yes, search + scan works in this case, but I'd be interested to know if it could be done with !memory vars

eg. if there is more than a single variable-length sequence in the overall pattern, using search and scan would produce all permutations of those sequences

(m/match {:foo [1 2 3 4]
          :bar [5 6 7 8]}
  {:foo [!n ...]
   :bar [!m ...]}
  [!n !m])
;; => [[1 2 3 4] [5 6 7 8]]

(m/search {:foo [1 2 3 4]
           :bar [5 6 7 8]}
  {:foo (m/scan ?n)
   :bar (m/scan ?m)}
  [?n ?m])
;; => ([1 5] [1 6] [1 7] [1 8] [2 5] [2 6] [2 7] [2 8] [3 5] [3 6] [3 7] [3 8] [4 5] [4 6] [4 7] [4 8])

Would this help?

(m/match [0 1 2 5 8]
         (m/and [!num ...]
                (m/let [?parity (map even? !num)]))
         [!num ?parity])

but it makes me wonder if the problem here is on the pattern or on substitution

The more I think about it, memory variables seem unsound in general

(m/rewrite [[:a 1] [:b 2] [:c 3]]
  [[!k !n] ...]
  [[!k !n (m/app str !n)] ...])
;; => [[:a 1 "2"] [:b 3 ""]]

This makes total sense operationally if you know that !n is just collecting and popping values

but it seems at odds with the declarative nature of the library

There are a lot of cases where you want that behavior. For example making tuples of things. Or inverting a matrix. I definitely understand how it can be counter intuitive. But I'm not sure what the semantics would be otherwise.

Yeah, I think it goes back to the "nesting" problem I was facing with the grouping construct - it's hard to differentiate where you want a variable to refer to a consistent value within a context, versus a sequence of things

there's also the matter of mixing the sequential nature of !memory vars with unordered hash-maps

(m/rewrite [1 2 3 4]
  [!n ...]
  {1 !n
   2 !n
   3 !n
   4 !n})
;; => {1 1, 2 2, 3 3, 4 4}

but

(m/rewrite [1 2 3 4 5 6 7 8 9]
  [!n ...]
  {1 !n
   2 !n
   3 !n
   4 !n
   5 !n
   6 !n
   7 !n
   8 !n
   9 !n})
;; => {7 2, 1 6, 4 3, 6 9, 3 5, 2 1, 9 7, 5 8, 8 4}

(I realise that's not a very realistic example, just trying to pick at the edges of the system to see if anything falls apart theoretically)

Yeah there are a lot of interactions between these things. There are ways to accomplish that without having to worry about order. On my phone but can show later if needed.

I would argue that memory variables are not actually at odds with declarative though. Really, its Meanders pattern evaluation strategy which is left to right, top to bottom.

An alternative universe of what a memory variable means: [thread incomming]

Declarative programming simply boils down to idea that the programmer need not worry about control flow.

Consider for a moment a magical f* function:

(defn f* [m]
  (m/search m
            (m/scan [?k1 (m/scan [?k2 ?v])])
            [?k1 ?k2 ?v]))

(f* {:a {1 "a1"
         2 "a2"}
     :b {3 "b3"}})

([:a 1 "a1"] [:a 2 "a2"] [:b 3 "b3"])

(defn f' [acc args]
  (assoc-in acc (butlast args) (last args)))

(let [!associations '([:a 1 "a1"] [:a 2 "a2"] [:b 3 "b3"])]
  (reduce f' {} !associations))

{:a {1 "a1", 2 "a2"}, :b {3 "b3"}}

What is going on here??

f*collected “variables” in an associative way which preserved information that current “memory variables” throws away

Specifically, when you nest memory variables, the collect values into arrays of different sizes, this explicitly removes the association information.

If in an alternate reality memory variables just did not work like this, we would have scoping.

What about f' ?? What’s the dealio there?

If we have “variables” in associative arrays, it becomes obvious how to substitute them associatively into a map: It’s just assoc-in!

Now there isn’t any meander syntax sugar for assoc-in that I’m aware of right now, but in a world where we have “associative nested memory variables” this operator would be uber powerful.

I don’t find it hard to imagine

(m/rewrite {!k1 {!k2 !v}}                      
           {!k2 {!k1 !v}})

That

is

some seriously nifty syntax!

I’ll take a different tact and say I don’t see this as non-declarative. Consider this example.

(m/rewrite [1 2 3 4 5 6]
  [!xs ...]
  [[!xs !xs] ...]

But it doesn’t have to us that syntax.

The core concept is the issue:

The discomfort shown in the map examples are due to Clojure. There’s nothing a lot I can do about that. & or m/and are the best offerings we have currently to get around the map ordering issue.

(m/and {1 !n} ,,, {9 !n})

{1 !n & {2 !n & {,,,}}}

How do you express collecting associative variables?

We could introduce a new concept “associative memory variables” maybe even a new symbol

If we say that [!n !n] meant repeat the exact same value twice, how do we get to the next value? Do we need to always say [!n ..2] or something like that? How does that work in the nested case? For example:

(m/rewrite [1 2 3 4 5 6]
  [!xs ...]
  {& [[!xs [!xs !xs]] ...]})

FWIW I’d rather memory variables just work the way I want them to hahahahahaa but of course that’s my opinion

For me, when I started thinking about those issues and how to solve them, the only answer I could come up with were explicitly imperative answers (like !xs.next).

That said, we do need good ways to to accomplish duplication just like we need good ways of doing grouping. We also (I believe) need good ways to generalize memory variables.

Call me a pedant but I think that variables are always declarative.

Memory variables were primarily driven to conception by regular expression things. I wouldn’t mind having an associative binding variable type, however.

They thing I want to discuss in this thread is that the nested memory variables drop information, useful information! If we had that information, we could do some cool stuff 🙂

I think we can generalize memory variables and do exactly what you are talking about. For a first approximation, memory variables are monoids. Why couldn’t we at least generalize that far?

But memory variables were not designed for nested things. They were designed for sequential things. We’re simply lacking a type for nested/hierarchical things.

I don’t think nesting is monoidal though.

You can also do {& [[1 !n] [2 !n] ,,, [9 !n]]}

I would imagine a monoidal map could serve many of those purposes, but I admit I’m just spit balling.

Any examples of symbolic and imperative programming combined? I think imperative is useful, but seems at odds with symbolic and transparent ways of doing things.

rewrite is that example.

The structure of clauses are basically if then else.

I guess we have different definitions of imperative. I don’t think if statements are an imperative construct.

I don’t like the word imperative. Its not really helpful here. What I’m trying to say is there is utility in “ordering mattering” and “order not mattering”.

What would this look like? I’m having trouble coming up with an sexpr kind of thing.

IMO it is way more elementary than any of that, its just fundamentally instead of producing different sized arrays, produce equal sized arrays. Maybe I’m guilty of jumping to an implementation here, but it just seems perfect 😛

(m/rewrite [1 2]
  (&scope-1 [?x ?y])
  (&scope-1 ?x))
;; => 1

(m/rewrite [1 2]
  (&scope-1 [?x ?y])
  (&scope-1 ?y))
;; => 2

(m/rewrite [[1 2] [3 4]]
  [[(&scope-1 [!x !y]) (&scope-2 [!x !y])] ...]
  [(&scope-1 !x) (&scope-2 !x) . !x ...])
;; =>
[1 3 1 3]

Maybe I’m missing the thread but it seems like the desire is to have a notion of storing things in contexts.

It seems entirely possible and useful to me to have a storage mechanism which is keyed by variables and their values and, in particular, for memory variables to have a distinct drain that belongs to that storage.

In the third example above there is the global !xs and !ys and then there is the “scoped” !xs and !ys that belong to &scope-1 and &scope-2.

(m/rewrite {!k1 {!k2 !v}}                      
           {!k2 {!k1 !v}})

(m/rewrite {:a {:b :c}}
  {!k1 {!k2 !v}}                      
  {!k2 {!k1 !v}})

I think you are presenting a (probably better) solution. I’m going to give a more direct example of what I’m pushing for specifically:

(m/match [[:a [[1 "a1"]
               [2 "a2"]]]
          [:b [[3 "b3"]]]]
         [[!k1 [[!k2 !v] ...]] ...]
         {:k1s !k1
          :k2s !k2
          :vs !v})

{:k1s [:a :b], :k2s [1 2 3], :vs ["a1" "a2" "b3"]}

{:k1s [:a :a :b], :k2s [1 2 3], :vs ["a1" "a2" "b3"]}

I’m happy to add map-of and set-of to epsilon so that folks can get this semantic easily.

I’ll call them “tim variables” just to distinguish the behavior, but fundamentally its just about how the arrays get populated.

LOL

map-of is a fine thing, but it doesn’t solve the information loss

Its not clear to me how !ks1 ends up with two :as.

Aha! That’s easy

Oh I see.

Yeah, I think the &scope thing I mentioned gets at your problem.

when we add something “nested”, we just also add whatever te current parent is.

so one algorithm is: • don’t insert tim variables if there are subvariables. • when inserting a bottom level variable, insert all the parents

This might not be a great way, I’m just describing something that would mechanically make sense to me.

So what would the result of this be?

(m/match [[:a [[1 "a1"]
               [2 "a2"]]]
          [:b [[3 "b3"]]]]
         [[!k1 [[_ !v] ...]] ...]
         {:k1s !k1
          :vs !v})

{!k1 ?x}

#{[!k1 ?x]}

The idea of a subanything implies a super something.

[!k1 ?x :as ?super]

@jimmy {:k1s [:a :a :b], :vs ["a1" "a2" "b3"]} @noprompt I don’t follow your notation. In my little world I’m only talking about sequences. Nested sequences are strictly identifiable. Map can always be represented as sequences. Maybe I confused things by eariler proposing a map syntax which isn’t really important to the question of how to keep context information. Also can you explain more what your $scope proposal is as I don’t understand the example.

Also just to brainstorm here, maybe we could use metadata on values in memory variables as a low friction alternative

@timothypratley That’s what I figured. But I am a little confused by why. Is !k2 and !v are subvariables of !k1. But I am confused on the relationship between !k2 and !v. They seem to be siblings, so they would both be bottom in my mind and cause double inserts. Is that not their relationship? Is !v a bottom variable but not !k2?

well “on values” is probably the wrong word there

Correct, they are both bottom siblings, and yes that implies that regardless of how many siblings exist, insertion into the parent stack should happen only once.

to explore a as metadata style instead of equal array sizesapproach a bit more; When inserting a memory variable, check to see if there is a parent, and just record that somewhere. The question for that approach is how do you identify parents? By value? by index? and where do you store it? in a shadow array? as an array attached as metadata to the variable maybe? Seems entirely feasible.

The hypothetical (&scope <pattern>) establishes a storage location &scope which maps variables in <pattern> to their values in <pattern> . Memory variables matched in a scope would be associated only with what the collected in that scope.

(m/match [1 2 3]
  [!xs (&scope !xs) !xs]
  {:global-!xs !xs
   :&scope-!xs (get &scope '!xs)})
;; =>
  {:global-!xs [1 2 3]
   :&scope-!xs [2]}

Of course we could’ve just written

[!xs (m/and !xs !ys) !xs]

I’m really confused, there is no sequence … and no nesting 😕 😱

Okay, lets back up here.

Lets go back to what I flagged earlier

[!xs !ys :as ?vector]

If we were going to imagine a super/sub relation ship here, we could say that !xs and !ys are subvariables of ?vector in this example.

But thats kind of weird so lets just say that !xs and !ys are subvariables of that vector.

The !xs and !ys are siblings and thus one is not a subvariable of the other.

The same is true if we talk about

{!ks !vs}

Logically, they are members of a pair.

I’m taking about Subsequencevariables: [!x [!y …] …] Clearly for every x there can be 0-n y That seems like a different concept to what you are describing

Right. And thats problematic if you want to keep things grouped.

So when we want to keep things grouped we need mechanism for establishing a group; an context sensitive association thing.

I claim that I’ve described two mechanical ways to preserve the context sensitive information purely on the pattern 😛

i.e. no syntax required to describe it.

I think what @noprompt means is that if we want to be able to choose between “to group or not to group” we need a way to distinguish these two situations.

Or if we want to group by something other than my parent

I don’t think we do need that; there are alternatives! 🙂 For example the metadata approach is just collecting more data… To chose to ignore it or use it happens later.

So you don’t strictly need to choose that in the pattern being matched.

You asked the right question earlier @timothypratley “how do you define what a parent is”?

Well taking the most basic case: [!x [!y …] …] Just by looking at it you can see that at the top level [_ _ …] has no sequence context around it, therefore !x has no “parent”. But when we look at !y it clearly occurs inside a surrounding sequence, so it has a “parent” !x. Programatically I imagine this logic as “I have a stack! Everytime I enter a sequence, I put that on the stack.

You don’t even have to think of them as parents at all really, just levels.

You’re saying !x is !y s uncle.

Or aunt.

More simply I’m saying that sequences can be nested.

But how would you square that notion with something like

[!x [!y] !x [!z]]

!x exists in a sequence, !y exists in a subsequence of that sequence.

there are no sequences in [!x [!y] !x [!z]] so nothing to square with that my small mind can see

By sequences, you mean repeats? (ie: …, ..2, ..!n, ..?n)

What about

[!x [!y] !y [!x]]

I mean repeats yeah, I guess sequence is a really bad word hahahaha. Loops

This is why I was saying earlier that the mechanism for expressing an binding scope is useful.

Right now there is only one scope: the global scope.

Every time there is a … it implies a very useful scope 😛

(m/match [[:a [[1 "a1"]
               [2 "a2"]]]
          [:b [[3 "b3"]]]]
  [[!k1 [[!k1.k2 !k1.v] ...]] ...]
  {:k1s !k1})

;; =>

{:k1s [:a [{:k2 1 :v "a1"} {:k2 2 :v "a2"}]
       :b [{:k2 3 :v "b3"}]]}

Yeah! that preserves the associative information in a very precise way 🙂

gosh I need to make a new language up just to talk about this stuff

There is a book on constraint language based on term rewriting that has a very similar construct. I have a book on it at home.

“nested repeat stack associativity information” how’s that sound lol

Ummm so where in the code would I look for where insertion into memory variables occurs?

Starting point https://github.com/noprompt/meander/blob/epsilon/src/meander/match/ir/epsilon.cljc#L1458

That change will be fairly difficult.

hahaha damnit!!!! well hopefully I’ll learn something.

Upon re-reading this thread I realize I never presented the KILLER FEATURE:

(defn f' [acc args]
  (assoc-in acc (reverse (butlast args)) (last args)))

(let [!associations '([:a 1 "a1"] [:a 2 "a2"] [:b 3 "b3"])]
  (reduce f' {} !associations))

{1 {:a "a1"}, 2 {:a "a2"}, 3 {:b "b3"}}

You could possible make that work as a rewrite over the ir. That wouldn't require changing the internals.

LOL with all the discussion today I didn’t get a chance to get into fixing the bug reported in #96.

New thread in which ridiculous escapades are journaled:

(defmethod compile* :mvr-append
  [ir fail kind]
  (let [!symbol (:symbol ir)]
    `(let [~!symbol (conj ~!symbol ~(compile* (:target ir) fail kind))
           ~'_ (prn "APPEND" ~!symbol)]
       ~(compile* (:then ir) fail kind))))

(defmethod compile* :mvr-bind
  [ir fail kind]
  `(let [~(:symbol ir) ~(compile* (:target ir) fail kind)
         ~'_ (prn "BIND" ~(:symbol ir))]
     ~(compile* (:then ir) fail kind)))

(do (prn "----------")
    (meander.epsilon/match
     [:x1 [:y1 [:z1]
           :y2 [:z2 :z3]]
      :x2 [:y2 [:z4 :z5 :z6]]]
     [!x [!y [!z ...] ...] ...]
     [!x !y !z]))

=>

"----------"
"APPEND" [:x1]
"APPEND" [:y1]
"BIND" [:z1]
"APPEND" [:y1 :y2]
"BIND" [:z1 :z2 :z3]
"APPEND" [:x1 :x2]
"APPEND" [:y1 :y2 :y2]
"BIND" [:z1 :z2 :z3 :z4 :z5 :z6]
=> [[:x1 :x2] [:y1 :y2 :y2] [:z1 :z2 :z3 :z4 :z5 :z6]]

what does append and bind mean? 😱 what things can I look up in ir?

Buried in some junk code I have a helper for analyzing stuff. https://github.com/jimmyhmiller/PlayGround/blob/master/wander/src/wander/core10.clj#L272

:mvr-bind is for binding a memory variable, usually to a [] but sometimes to (vec seq).

Not 100% accurate but useful.

:mvr-append is for conjing on it.

Sorry its not documented. 🙂

@jimmy ooo nice thank you I’ll play around with that @noprompt I’m probably conflating something but it seems surprising (in a wierdly good way) that my output indicates that !x and !y are appended to, but !z is bound to… I’m obviously misinterpreting the output though.

Because z is just a literal vector. We can just bind it. It's basically an optimization.

ohic

Just caught up with all the threads, I'm happy to have sparked so much discussion 😅

I really like the !k1.k2 notation and the idea of explicitly declared scopes