Hey guys, I should have shared this here a long time ago. I'm building a visual programming language/game entirely in clojure, what do you think? https://mockmechanics.com/ Using it I built a working piano, a combination lock, a bubble sort machine, even tetris, all without any code, you can see these machines and more on my YouTube channel. Here's the latest thing I was able to build inside it without using any code, a punched cards programmable 3d printer. Follow me on twitter if you want to keep up with what I'm doing next https://twitter.com/MockMechanics

Does anyone know of any tools that allow you to enumerate the ordering states created by a set of asynchronous processes and some causality statements? e.g.

a causes b
a causes c
b causes d
c caused d

results in

a -> b -> c -> d -> d
a -> c -> b -> d -> d
...

I’m not even sure where to begin looking

my goal is to help me ensure I’m accounting for all ordering possibilities when thinking through changes to a distributed system

@him This might just be a topological sort? This library can calculate it for you: https://github.com/stuartsierra/dependency

topological sorting is 1. Great 2. Not complicated enough to pull in a library for https://gist.github.com/hiredman/71b71e4e07e7666fe1b9def9a476c765#file-lrun-clj-L1-L10 and https://gist.github.com/hiredman/075b45eaeb01e4b526ce6f8854685487#file-ur-component-clj-L1-L10 both include the same topo function at the top which does the sorting

I guess "requires a DAG" should go on the list somewhere

I bet with some tinkering you could tweak that function to instead of returning a single ordering, return a set of all the possible orderings

> I bet with some tinkering you could tweak that function to instead of returning a single ordering, return a set of all the possible orderings Yeah was just gonna say, toposort misses on that requirement. But good idea, I’ll run with that.

I feel like I want 1% of the Bloom programming language 🙃

depending on what you are doing https://github.com/jepsen-io/elle or https://github.com/jepsen-io/knossos might be of interest

I don't know a library that already does this (maybe one of the ones suggested already does), but in terms of graph theory terminology you are asking to enumerate all possible topological sorted orders of an input graph.

Finding one such topological sorted order is easy to do in linear time. Enumerating all possible ones can probably be done in linear time in the length of the output, but for N nodes the number of such topological orders can be as large as N! (for 0 edges/constraints).

Thanks @andy.fingerhut, I hadn’t considered that. Fortunately for me, N is small (~5), but still big enough (given N!) that mentally tracking possibilities is impossible.

I guess this is one reason why designing correct distributed systems is hard…

For N small enough, a perfectly quick hack approach is to generate all N! permutations, and remove any that violate one of the causality constraints.

oh that’s clever!

My fist core logic program cc @him

(use 'clojure.core.logic)

(defne arco [x y]
  ([:a :b])
  ([:a :c])
  ([:c :d])
  ([:b :e])
  ([:c :e])
  ([:d :e]))

(defn patho [l]
  (conde
   [(== l [:e])]
   [(fresh [d x y]
      (firsto l x)
      (resto l d)
      (firsto d y)
      (arco x y)
      (patho d))]))

(run* [q]
  (firsto q :a)
  (patho q))
;; => ((:a :b :e) (:a :c :e) (:a :c :d :e))

whooaaaa! nice!