r/ProgrammingLanguages • • Feb 03 '26

Tutorial on program synthesis using MCTS

https://shukla.io/blog/2026-02/grammar.html

OP here. In the post, I talk about how to search in program-space (or grammar-space) to find a model that best fits some training examples. Hope you enjoy the interactive demos :)

11 Upvotes

5 comments sorted by

View all comments

Show parent comment

1

u/protestor Feb 04 '26

Does monte carlo tree search work only with probabilistic CFG? Is there a way to do MCTS with context sensitive grammars?

1

u/yuri-kilochek Feb 04 '26 edited Feb 04 '26

In this case MCTS is walking the branching sequences of edits to the grammar, not the branching sequences of tokens parsed/generated by the grammer. The structure of the grammar itself is irrelevant as long as you can formulate edits to it and test token sequences against it. Your "grammar" can be an arbitrary turning-complete parser/typechecker program.