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

Diffusion on syntax trees for program synthesis

tree-diffusion.github.io

Post reply on HN
Print view View original

91–95 of 95 posts

Re: Diffusion on syntax trees for program synthesis

#91

Post by robxorb »

pama wrote: post #69
robxorb wrote: post #67

Earlier quoted context omitted.

I've read it in several places over the years, and just had a search now to find a reference to cite. Here's a PubMed paper on the subject: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3010799/ (And note how points 1 through 4 all quite conflict with each other!)

If it helps think of the first author as the lead engineer or the CEO, and the last author as the board or the VC. In some areas of science (or some teams) the last author is closer to a CEO, in others closer to a VC (they almost always have the powers of the board). This picture does not contradict the guideline in the reference you shared. Typically, most of the work and writing of the paper is done by the first au…

That does help, thanks! Very intuitive analogy. Maybe this kind of organisational structure is a kind of natural archetype people gravitate towards when coming together to break new ground.

Re: Diffusion on syntax trees for program synthesis

#92

Post by hoosieree »

can16358p wrote: post #59

I wonder how this would apply to compiler/interpreter optimizations. Is it possible that it can "disect" some parts of the execution, perhaps at assembly level, and come up with optimizations specific to the compiled code without changing the output (I mean expected program output, not emitted binary), that modern compilers have not deterministically come up with?

My dissertation worked on a similar problem. I used obfuscation to build a large dataset from a small set of ground-truth functions. Then built a model to classify unseen obfuscated binary code to the nearest of the known functions.

The application I had in mind during the research was anti-malware static analysis, but optimization is really just the flipside of obfuscation. Something I'd like to try in the future is a diffusion model that treats obfuscation as "noise" to be removed.

One thing I learned is that optimizing compilers produce very regular output. After normalizing addresses, the "vocabulary" size of basic blocks ends up pretty small, like ~2000 tokens. Certain "phrases" correlate with the original source code's semantics regardless of how much obfuscation you add on top.

Re: Diffusion on syntax trees for program synthesis

#93

Post by teruakohatu »

Chabsff wrote: post #78
teruakohatu wrote: post #49

Earlier quoted context omitted.

These kind of Genetic Algorithms are still being researched in academia. I attended a seminar a couple of years ago on the subject. It’s still a total dead end imho.

I used to (early 00s) be super big into GA and GP until a professor of mine at the time described the whole class of algorithms as "Marginally better than brute forcing". That really resonated with my experience, and was just too spot-on to ignore.

I remember coming to the same realisation :)

Re: Diffusion on syntax trees for program synthesis

#94

Post by marcelroed »

JHonaker wrote: post #73

Markov Chain Monte Carlo for program synthesis isn't exactly novel. The most immediate reference I thought of is Josh Tenenbaum's [1]. There's also a lot of demos in WebPPL (web probabilistic programming language)[2] like [3] for the synthesis of 3D space-ships. I highly recommend their associated books on The Design and Implementation of Probabilistic Programming Languages [4] and Probabilistic Models of Cognition […

It’s worth noting that Shreyas (the first author) was a student with Tenenbaum at MIT before he went to Berkeley

Re: Diffusion on syntax trees for program synthesis

#95

Post by randcraw »

Philpax wrote: post #70
whereismyacc wrote: post #68

Earlier quoted context omitted.

I guess the output would be an llvm intermediate representation that you can compile down and run, right? I'm stretching pretty far past my knowledge here.

I think the question - at least, for me - is "what do you expect to do with this system?" What will you output with your diffusion model?

An AST or any intermediate representation of an input language isn't strictly necessary for a translation task. But if you want a human to understand the translation, an IR can go a long way to illustrate the translation process into a human comprehensible form. The transformations of the tree can also provide insight into the various translation activities and alternatives, like translation from one human spoken language into another (text or voice), from one musical style into another (in notation or audio), or source code into executable with multiple optimization steps. Without the AST (IR), the human must remain out of the loop, relegated to being a bystander mystified by the inexplicable magic taking place inside the automated translator.
Post reply on HN