On Sun, Jul 10, 2016 at 6:04 AM, Mark Engelberg <mark.engelb...@gmail.com> wrote:
> > This isn't due to anything inherent in clojure.spec, it's just that for > non-trivial functions, coming up with relevant random input is a very hard > problem. > This is a very interesting observation. I've written generators (we'd call it enumeration) for a fair number of computational systems when I was at Wolfram, so I have some observations and suggestions. This problem comes up anytime the *behavior* of the function is nontrivial. For most human-coded functions, behavior is trivial, its only the implementation that is nontrivial. Clojure.spec optimizes for this case. All NP-complete problems, by definition, exhibit a kind of universality, meaning they can be programmed. In general there is no way to know the behavior of the inputs without an irreducible amount of computation. In specific cases, there are ornate mathematical theories, which can also help with generation, but which have no unifying framework universal across all systems. So I don't think there is any general solution clojure.spec can offer. On generating formulas: I would just enumerate them systematically with increasing number of variables (starting at 1), and see how far I can get within an allotted runtime. Being able to time-out surely must be important also. With most nontrivial computational systems you don't have go far to hit nontrivial behavior. So only being able to enumerate to a modest size isn't a deal breaker. If you want to generate big, satisfiable formulas, i think you'll have to make them satisfiable by construction. You can do with this with a simple term-rewriting system. Anytime you have a satisfiable expr, you can "or-in" failing branches. It would actually probably be pretty illuminating so see the runtime performance under various schemas for doing this. If the goal is to test with a diverse set of formulas, your best bet is to generate them using using a secondary computational system (for the elementary cellular automata) and then map its behavior into formulas. You might find the following links interesting, both for potential methods and for building intuition of what might one expect when enumerating through mathematical systems: http://www.wolframscience.com/nksonline/section-12.9 http://www.wolframscience.com/nksonline/notes-section-12.9 -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
