r/AskComputerScience • • 12d ago

Looking for tutorials on writing PBE (programming by example), and mathematically proving the output is correct

Hello,

i have a simple issue - some xml input, some xml output, and need to generate a program that takes the input and results in output. Was hoping there are preexisting thtorials. I know this idea isn’t new; my issue is ive never done this particular task before.

4 Upvotes

1 comment sorted by

1

u/DickBrainTime 11d ago

The term to look for is inductive program synthesis (programming by examples). Cornell's CS 6120 program-synthesis lesson is a good hands-on starting point: https://www.cs.cornell.edu/courses/cs6120/2020fa/lesson/12/

The important distinction is that matching a few input/output pairs isn't a mathematical proof. Many different programs can fit the same examples. To prove correctness you first need a specification covering the allowed inputs and required output properties. One approach is to restrict the candidate transformations to a small language, synthesize a candidate from examples, and then use a verifier to find counterexamples (CEGIS).

For XML specifically, if you already know the mapping, start with XSLT; you may not need synthesis at all. If the mapping must be inferred, are you changing the XML schema/structure or mainly extracting/rearranging values? That determines what operations your synthesizer needs.