Fork me on GitHub

How would I go about writing a spec for a data structure that detects (disallows) cycles? Context: As a fun learning project I’ve been writing a state machine for a lexer, as a map from states->inputs->[outputs/->states] (that last part is the transition). Now as is typical for these, some of the transitions are similar on different states (here because of lexemes). Instead of composing the map programmatically I thought I invent an additional behaviour and add a :with key on the transition, to say that the output is combined with the output of another transition. This way the state machine is fully described as a plain data-structure. :with merely points to The terrible thing here is that I introduced the possibility for recursion/infinite loops. So my intuition is that I can write a spec that detects cycles, but I cannot really wrap my head around it. Is this possible? My context is just an example, maybe the design is wrong, but I would be generally interested in applying spec this way and how one would go about it.

Alex Miller (Clojure team)22:07:52

I think I would probably not write such a spec

Alex Miller (Clojure team)22:07:29

but a spec can be any predicate function

Alex Miller (Clojure team)22:07:53

so if you can write a function (no-cycles? data-structure), then that's a valid spec


right I was getting stuck somehow in trying to make the spec both check the structure and detect the cycle at the same time


but there is s/and

Alex Miller (Clojure team)22:07:46

(s/and ::structure no-cycles?)


right ty 😄


you think such a spec is a smell?

Alex Miller (Clojure team)22:07:49

I just don't think you're getting any value out of using spec to write that :)

Alex Miller (Clojure team)22:07:54

spec's sweet spot is describing information structures (maps of attributes) or syntactic structures (sequential regex type things). the more generic or abstract you get from that, the less value you get


I get what you’re saying. But say I used spec during development time with instrumentation I would still get value from this right?

Alex Miller (Clojure team)22:07:50

keep in mind that slow specs can really slow down execution. cycle checking sounds slow. :)

Alex Miller (Clojure team)22:07:07

would you be better off preventing a graph with a cycle from being created in the first place?

👍 2

I just started reading a book that thematises this. I have to think about this more deeply! ty