Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: MarkovJunior, PPL based on pattern matching and constraint propagation

github.com

Post reply on HN
Print view View original

11–15 of 15 posts

Re: Show HN: MarkovJunior, PPL based on pattern matching and constraint propagation

#11

Post by 331c8c71 »

ExUtumno wrote: post #7
331c8c71 wrote: post #3

Fascinating. One of the few things posted here that got me really excited! Probably because I studied the basics of Markov algorithms, but I never imagined the idea could be developed further in such an interesting way.

Thanks! I would have probably never known about Markov algorithms if I were not taught them in 8th grade =)

You must've gone to a special math school or smth) I learned about them in the uni and as with 90% of material it was quite dry and formal. Pretty sure they don't talk about generative art while teaching them in 2022 (and they probably should:).

Re: Show HN: MarkovJunior, PPL based on pattern matching and constraint propagation

#12

Post by sitkack »

ExUtumno wrote: post #6
sitkack wrote: post #4

This is phenomenal! I have been toying with similar ideas, and I am so glad you are the same person behind Wave Function Collapse [1] . The fact that you have lifted the technique into a programming language is immensely powerful. Where do you want to go with it? What research or other projects have been impactful on this work? From the author, 40 minutes of the algorithm running through examples. [2] Past stories ab…

Thank you! For MarkovJunior, the recent projects that were impactful the most were Imagegram by Guilherme S. Tows [1] and Daniel Ritchie's dissertation [2] about PPLs for procgen. I took quite a different approach from Ritchie's though. [1] https://zaratustra.itch.io/imagegram [2] https://dritchie.github.io/pdf/thesis.pdf

That thesis is really fun, but it will take me a couple weeks to digest. Before it even starts I see Pat Hanrahan, who is one of the nicest most creative people I have met in CS (), I know this going to be good.

A fantasy of mine is to have a bag of arbitrary constraints and behaviors of agents that exercise the system. One could sketch a building, model the behavior of people that will use it and let the system run, doing backwards and forwards inference to evolve a structure that makes those agents satisfied across lots of criteria. The designer if they are still called that, can select designs they like and the system can use that as a seed or test oracle. Virtual cows, cow paths and evolvable structures wrt those cow paths.

What do you think of "Growing Neural Cellular Automata" [1]

Are you by chance following CadQuery? [2]

[1] https://distill.pub/2020/growing-ca/

[2] https://github.com/CadQuery/cadquery

Re: Show HN: MarkovJunior, PPL based on pattern matching and constraint propagation

#14

Post by olvy0 »

Just an idea: this or something similar could be utilized to generate test vectors, for property based testing [0]. Also for model-based testing, if you consider the model to be a vector of actions [1]

Currently, AFAIK, property based testing relies on mostly random generation of input vectors. It's possible to "shape" those vectors into other data structures such as trees [2] and it's the way it's usually done, but it's difficult and error-prone for more complex inputs.

There's also the option to filter each vector before running, or, after running, by performing the shrinking algorithm to produce the minimal input vector that reproduces the problem.

When I tried using property based testing for my use-case, as a model-based testing, I had to write code to filter most of the random test vectors since they weren't relevant, they didn't make sense.

So it might be possible to guide the generation of the input vectors so they'll be less random, and save time during run.

[0] https://typeable.io/blog/2021-08-09-pbt

[1] https://fscheck.github.io/FsCheck/StatefulTesting.html

[2] https://www.stackbuilders.com/blog/a-quickcheck-tutorial-gen...

Re: Show HN: MarkovJunior, PPL based on pattern matching and constraint propagation

#15

Post by olvy0 »

kertoip_1 wrote: post #8

Most satisfying animations I've seen in a long time. I just can't stop staring at them, they are wonderful. Are there any other possible use cases of this language other then image or maybe in-game world generation? Do you consider it just as an interesting academic problem or do you plan to use it somewhere?

Maybe for generating more useful input vectors for property-based testing? I wrote about this in another comment here [0]

[0] https://news.ycombinator.com/item?id=31704791

Post reply on HN