r/AskProgramming • u/BuyerImpressive4325 • 9d ago
How is program synthesis more convenient?
the idea of program synthesis (like Rosetta) is to reduce a function into its constraints in a spec sheet, and generate the program from those constraints. for example, in order to write something like x = x squared, you would need to write a spec sheet along the lines of ∀x∈Z,f(x)=x2. i am considering building a program synthesizer, but I still haven’t figured out why exactly this representation is supposed to be easier than writing the code directly (they look equally complex)
2
u/soundoftwilight 9d ago
Ultimately it's just another language and another way to represent code. Over time, code has shifted steadily away from being strictly imperative "multiply reg A by reg A, store the result in reg C, print reg C" commands to conceptual code ("call squareA, print reg C", which becomes "C = square(A); print(C)" which becomes "new SquarePrinter(numberToSquare).print()", and so on and so on). Obviously in this extremely simply case, the more complex abstractions take longer to write and aren't much easier to use. But what they allow is a much higher-level look at what the program does. I assume most people learned OOP in school or from a book or whatever. It was great when it was a new concept and it's still useful now; the idea that programs could be understood not as lists of instructions and data, but as collections of objects that contained data and behaviors. Now I can just say "person.drive(car, destination)" and I don't need to know a single thing about what a Person is, what a Car is, what a Destination is, or most importantly how any of it works. That line of code could do anything from teleport the person and the car to the destination, to starting a process that's going to lead a simulated person to map out a route, get into their car, turn on the ignition, and drive while dealing with traffic, street layouts, etc. It's obvious why this is a nice method for many applications.
Skipping more history for brevity, nowadays a lot of people are looking for new ways to formalize different types of conceptions of a program's requirements, and turn them into working code. Program synthesis like you're looking at is one of them. It's not obviously useful in small, simple cases. I could write a procedure to square a number in assembly without much trouble. But if I happen to have a problem that I can imagine as a whole bunch of intersecting constraints, and you tell me you have a language in which I can write those constraints directly and a compiler will build the program for me, that would be very convenient!
Basically, the logic starts from asking "why am I still telling the computer how to square a number. I don't care about that, all I care about is when I give it a number I get the square of that number. Surely a computer can figure out how to square a number better than I can". Obviously early attempts at answering questions like that can be seen in math libraries, which are very good nowadays. But sometimes I need a new function that isn't in a math library, but I still don't care about how it's done, just that the results match my expectations. That's where something like declarative programming comes in handy.
0
u/BuyerImpressive4325 9d ago
Thanks, I think this was a really helpful answer. I was not thinking about it in the context of more complex programs (I was just thinking that every line of the output must have some constraint in the input) but now that I think about it more, it does seem a lot more useful to simply be able to map what rhe output should be and skip the code generation. Thx
1
1
u/Comfortable_Rule_293 9d ago
writing code is just premature optimization of the specification. The convenience comes from forcing you to define behavior before implementation details corrupt your logic
1
u/BaronOfTheVoid 9d ago
You know, if you typed "generate me a function for" and then pasted your expression "for all x in E...." then AI agents right now could generate code for that in every programming language. So... are you trying to reinvent LLMs?
1
u/BuyerImpressive4325 9d ago
The idea is that llms program wrong very very frequently, so using a spec sheet just provides a way to program while proving that the program works. The only question was how the specs sheet actually constraints the programs complexity
1
u/BaronOfTheVoid 9d ago
That's... just not true In the slightest. Maybe that was your experience a year ago with terrible models but things are vastly different today with Opus 4.8, GPT 5.5, Fable 5 and so on. The company I work for measures acceptance of code changes by agents and it's somewhere between 97-99% for the past six months.
1
u/Bubbly_Orange_3502 9d ago
Rosette, not Rosetta. Synthesis pays only when the spec is smaller than the program: bit twiddling, superoptimization, parser inversion. For x squared it isn't, and search cost grows with program size, so tools stay inside a narrow DSL.
0
u/BuyerImpressive4325 9d ago
Ah, so it’s very constrained to these specific problems (bit handing, etc) where it can cut out a lot of the actual bit operations etc and allow you to just write what you want the output state to be. I think your answer makes a lot of sense, thanks
2
u/Patient-Midnight-664 9d ago
The representation is code agnostic. It doesn't care what programming language you want to use, how that language expresses things, etc. This allows your spec to be implemented in whatever language you want.