[opless]

Ah, I read the first link in the comments first, which really does imply they're using GP methods.

https://homes.cs.washington.edu/~bornholt/post/synthesis-exp...

However they're using a SMT solver as part of the fitness function of the program.

You know - it needs the correct output, but you need to prevent overfitting, and if you have a formal proof of the program generated you can expend greater effort into reducing its complexity and optimising.

Again, it's an old new thing and possibly going to start getting hyped like neural networks have been of late.

[seanmcdirmid]

I’m sure the term program synthesis precedes the term genetic programming. Neither of these are new things. This (https://www.sri.com/sites/default/files/uploads/publications...) is from 1971, for example. The earliest reference I can find to genetic programming is in the early 90s.

There are plenty of program synthesis techniques (maybe not this one) that do not use fitness functions and get the program straight from a solver. If they have anything written up, I’m sure the related work section would make the context more clear.

As for the accusation of band wagoning, it seems to come straight from the community that has been doing synthesis for years, not the ones that do GP.

[ychen306]

    Ah, I read the first link in the comments first, which really does imply they're using GP methods.

No, it doesn't.

[opless]

And the evidence to back up your assertion, is where?

Here's mine... (excuse my lack of formatting.)

The synthesis step of stochastic superoptimisation finds the next candidate program P’ by drawing an MCMC sample based on the previous candidate program P. It proposes P’ by randomly applying one of a few mutations to P:

* changing the opcode of a randomly selected instruction

* changing a random operand of a randomly selected instruction

* inserting a new random instruction

* swapping two randomly selected instructions

* deleting an existing randomly selected instruction

The MCMC sampler uses the cost function, which measures how “close” to the target program P’ is and how fast P’ is, to decide whether to accept the candidate P’. A candidate is more likely to be accepted if it is close to the target or very fast. But even programs that are slow or distant from the target have some probability of being accepted, ensuring we explore novel programs

[ychen306]

There's nothing "genetic" about how MCMC works. AFAIK, usually with GP, you keep multiple candidates that you evolve together, which is not the case here (it's much closer to metaheuristics such as Simulated Annealing), e.g.:

  let candidate be some random program
  while candidate not correct (per your SMT solver):
      new_candidate = mutate candidate
      let cost be cost of new_candidate
         (varies by different techniques;
          some just measure the number of bits differ
          from expected output of testcases)
      if cost is improved:
         candidate = new_candidate
      else, with some probability (the lower the cost, the higher the prob.):
         candidate = new_candidate

Of course, there's nothing preventing you from using GP instead of MCMC to find programs. The focus of research is on how to mutate (e.g. how do you avoid generating bad candidates based on past experience) and evlaute the cost of a candidate, rather than the methaheuristics itself.

[voidmain]

That looks to me almost exactly like a (1,1) evolution strategy [1]. Our field frequently has invented almost the same ideas multiple times in different subfields, with different mathematical analogies and different terminology. It's useful to identify these connections, and it helps not to be automatically dismissive of people who seem to be using the "wrong" terminology.

[1] https://en.wikipedia.org/wiki/Evolution_strategy

[opless]

Perhaps I should not have been so hasty.

It's just annoying that the implication is that the 'reinventors' haven't done their research. It's almost as bad as my original feeling of "that's an new old thing", and assuming malicious intent/plagiarism.

[TheOtherHobbes]

That looks very GP-ish, but - as with all GP - the usefulness of the outputs depends on the sophistication of the cost function.

What does "close" mean here? I don't see that explained.

If you're trying to match outputs, then this is just old-fashioned GP with a minor twist - i.e. including speed in the fitness function, which has the potential to find some novel local maxima, which produce outputs that are close to the target AND very fast.

If you're trying to match instruction sequences - then I don't see the point at all.

GP often fails because it runs out of steam before producing a definitively correct solution.

It's easy to design cost/fitness functions that get close but not close enough, and slightly harder to design functions that solve a non-trivial problem some of the time.

It's incredibly hard to design functions that find an answer reliably without getting lost in the problem space.

[opless]

+1