Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building a Program Synthesizer

homes.cs.washington.edu

Post reply on HN
Print view View original

21–27 of 27 posts

Re: Building a Program Synthesizer

#21

Post by tobmlt »

iancmceachern wrote: post #9
jnurmine wrote: post #5

Once upon a time I thought of this and came to a conclusion that in the future software is not written, it is grown. A big hall with computers, churning on calculations to end up with reusable modules/components for some predescribed purpose. These are combined and eventually larger systems emerge. The inputs to the calculations were to be descriptions of what the program should do, no details on the "how". For insta…

This is happening now for mechanical design. They call it generative design. You give inputs (volume/shape, loading cases, other parameters) and then the software iteratively solves for the optimum geometry to meet the goals.

And there is also ``form parameter design'' for ship hull geometry. It is also generative, but perhaps it more typically makes use of deterministic (nonlinear optimization) solvers to generate the geometry itself. (Implementations vary - I show my bias (or just inability to shut up) here as I am trying to finish a PhD in this as we speak) The main similarity I'm going for in this comment is that the user specifies design constraints and the program generates ship hull shapes that meet those requirements.

Tie generative methods in with solvers for hydrodynamics, motions, structures, stability, etc, and one can conceive of automating the ship hull design spiral, or sections of it anyway. That's not to say that some of this is not already out there in commercial software.

Re: Building a Program Synthesizer

#22

Post by TheOtherHobbes »

opless wrote: post #19
ychen306 wrote: post #18

Earlier quoted context omitted.

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

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…

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.

Re: Building a Program Synthesizer

#23

Post by dluan »

jnurmine wrote: post #5

Once upon a time I thought of this and came to a conclusion that in the future software is not written, it is grown. A big hall with computers, churning on calculations to end up with reusable modules/components for some predescribed purpose. These are combined and eventually larger systems emerge. The inputs to the calculations were to be descriptions of what the program should do, no details on the "how". For insta…

In a way, programs have evolved, just very slowly because the evolutionary pressure was from developers, whose speed and effectiveness is a bit random. Most codebases are like little cells, with pockets of non-coding technical debt still influencing the epigenetics of the software's future designs...

Re: Building a Program Synthesizer

#24

Post by ychen306 »

opless wrote: post #19
ychen306 wrote: post #18

Earlier quoted context omitted.

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

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…

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.

Re: Building a Program Synthesizer

#25

Post by voidmain »

ychen306 wrote: post #24
opless wrote: post #19

Earlier quoted context omitted.

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…

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 j…

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

Re: Building a Program Synthesizer

#26

Post by opless »

TheOtherHobbes wrote: post #22
opless wrote: post #19

Earlier quoted context omitted.

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…

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…

+1

Re: Building a Program Synthesizer

#27

Post by opless »

voidmain wrote: post #25
ychen306 wrote: post #24

Earlier quoted context omitted.

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 j…

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_…

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.

Post reply on HN