> There, the ocean-exploration organization Deep has embarked on a multiyear quest to enable scientists to live on the seafloor at depths up to 200 meters for weeks, months, and possibly even years.

Most techniques are essentially brute force enumeration with tricks to improve performance, so they tend to struggle to find larger programs. A lot of active research is in improving performance.

Compared to asking a LLM to write a program, program synthesis approaches will guarantee that a solution will satisfy the specification which can be very powerful.

In particular, as the author has discovered, one area where program synthesis excels is finding small intricate bitwise operator heavy programs that can be hard to reason about as a human.

The most famous example of program synthesis is Microsoft's FlashFill, which is used in Excel. You give it a few input output examples and FlashFill will try to create a small program to generalize them, and you can apply the program to more inputs, which saves you a bunch of time. An example from the paper is:

  Input -> Output

  International Business Machines -> IBM
  Principles Of Programming Languages -> POPL
  International Conference on Software Engineering -> ICSE

  String Program: Loop(\w : Concatenate(SubStr2(v_1, UpperTok, w)))

EUSOLVER: https://www.cis.upenn.edu/~alur/Tacas17.pdf

FlashFill: https://www.microsoft.com/en-us/research/wp-content/uploads/...

BlinkFill: https://www.vldb.org/pvldb/vol9/p816-singh.pdf

Synquid: https://cseweb.ucsd.edu/~npolikarpova/publications/pldi16.pd...