How AI based programming could work
bjenik.com
bjenik.com
An example of work showcased at this year's PLDI that's capable of doing this sort of stuff:
Fast synthesis of fast collections (https://homes.cs.washington.edu/~mernst/pubs/collection-synt...): specify a database-like data structure for a collection of objects and the list of queries performed on that data structure, and get out code that's as fast as hand-tuned data structures with fewer bugs.
Programmatic and Direct Manipulation, Together at Last (http://dl.acm.org/citation.cfm?id=2908103&dl=ACM&coll=DL&CFI...): Take an image generated by code (e.g., periodic stripes), and be able to manipulate that image by drag-and-drop, e.g., changing stripe size or period.
Stratified synthesis: automatically learning the x86-64 instruction set (https://stefanheule.com/publications/pldi16-strata/): 60% of the x86-64 instruction set can be formally specified starting from about 60 base or pseudo-instructions (basically, describing each instruction as an assembly program of simpler instructions).
In fact there is already a lot of solid work just on this subject:
* Learning algorithms from examples http://arxiv.org/abs/1511.07275 https://arxiv.org/abs/1410.5401
* Generating source code from natural language description http://arxiv.org/abs/1510.07211
* And, the most closest work to what author probably wants, a way to write a program in forth while leaving some functions as neural blackboxes to be learned from examples: http://arxiv.org/abs/1605.06640
* Also there is a whole research program by nothing less than Facebook AI Research that explicitly aims at creating a conversational AI agent that is able to translate user's natural language orders into programs (asking to the user additional questions if necessary): http://arxiv.org/abs/1511.08130 (there is also a summary here http://colinraffel.com/wiki/a_roadmap_towards_machine_intell... )
And deepmind is also working on conversational agents: https://youtu.be/vQXAsdMa_8A?t=1265
Given current success of such models, automating simple programming tasks maybe not as much research as engineering and scaling up problem.
There is a lot of exciting machine learning research out there nowadays. Almost all of this research is available for free from papers posted on arxiv. It is a really good idea to read more about state of the art before coming with new ideas.
A lot of the "using AI for programming" papers (AI in this case being anything from nets to logic stuff) focus on building these small parts - I'm more interested in the levels above that. The "generating code from natural language/dialogs" also kind of misses my idea as it still assumes a "programmer" to tell it what to do (in the amazon example "display the products on a grid" or "make the buy button bigger"). The programmer would in this case either guess the right thing ("everybody has their products in a grid") or run something like A/B testing against some metric ("items sold" or "$ revenue") and then go back to the conversational programming tool and tell it "change the button". Why not skip the programmer and give the metric directly to the net? The thing I would like to get working is telling the net "here is a ton of different buttons, grids, lists and a lot of other UI stuff, and there are all our products - I want to maximize revenue - do whatever you like to get there".
Regarding the vague ideas: I believe (also totally unsubstantiated - though research in this area would be quite interesting) that writing down ideas first and then looking into them (either by reading other papers or doing own research) is far better than the other way round, because it has a higher probability of leading to something new, because you don't follow assumptions and errors others potentially made which could lead to a dead end. Of course there is a certain trade off, because if you try to reinvent everything you will not get to the point of something new.
As you referenced in your footnote, this goal is a little like the goal of putting a man on the moon, if the year is 1900. One could the make the case that something resembling an AGI agent would be needed to design/manage a merchant website with any degree of introspection and customizability. Your machine would need to understand business objectives, UI patterns, aesthetics, etc before taking the helm, and these things take years to learn even for even humans. This is not to say that AGI isn't an admirable goal, but that it's an obvious one, just as I imagine reaching the moon was in the centuries leading up to 1969.
Scientific research is certainly a massively parallel effort, pushing the boundary of our knowledge in many different direction at once, but rest assured that there are many good men and women working in this specific direction.
(also know that I have a lot of respect for this kind of vision-oriented thinking, especially because it generally leaves the writer vulnerable to criticism like this)
Every ML problem has a lot of algorithms that can be applied to it to solve it. Previously unsolvable problem (e.g. learning playing atari game from pixels) can become solvable if a better ML algorithm is devised, more compute power is applied, or the problem is simplified (maybe with data augmentation or feature engineering, or constraining the domain).
I think the problem you are stating - finding the best configuration of website to extract more ad revenue - can be simplified until it is solvable by currently available algorithms and hardware. Big companies are already doing similar things - Google uses reinforcement learning to recommend new items on its services, Facebook is known to use machine learning to somehow make more profit from users.
Given expert knowledge of the problem and good algorithms, it can be solved in some form, that's my point here.
Can you mention any key papers about NNs that manipulate existing code? e.g. parse it, find design pattern, optimize, etc I think this is just as interesting and already feasible.
>NNs that manipulate existing code? e.g. parse it, find design pattern, optimize
Also: you probably shouldn't need special architectures for such problems, these can be solved by seq2seq, NTM, RL-NTM and such, given a good dataset. Such tasks are still beyond current state of art though, it seems.
If you want to write a vague and generic piece of code that can figure out by itself what it is that its outputs ought to be with regards to its inputs, you are, with effect, creating artificial intelligence.
This, in turn, requires teaching.
What if suddenly you have new pages on your website? Your AI program thingy wouldn't be able to serve them until you taught it what these pages are and in what situations the end user might be interested in viewing them. Imagine having a 5 year old kid handling your shop's cashier. And now a new product arrived and you have to explain to him/her that there's this new product, what it's called, the price and which types of people are allowed to buy it (e.g., alcohol couldn't be sold to people younger than X years old). If you're really teaching your application with natural language, like you would with a five year old, then the effort it'd take to get that info into your system would defeat the purpose of actually using a computer to do it (computers are good at storing and looking up stuff in large data sets, better than humans for really large data sets).
This whole hype of machine learning is suitable for situations where you have large amounts of data and you want them crunched according to some basic pre-established and non-changing logic without relying on actual human labor. If the logic evolves, you'll always require humans to sit at the helm and steer the right and wrong.
My 2 cents.
Do not underestimate what good ML model can learn given enough data. And in case of online shopping there usually is more than enough data, and big companies like Amazon have been using ML (context bandits) for quite some time.
In my app, 7 Second Meditation, I am constantly authoring new content. It uses improve.ai to show that new content to some small number of users and learn how they react to that content.
The learning happens from the users themselves. In my particular case, within about 300-500 views the system can tell if a new piece of content is total crap and will basically stop showing it. If the content is amazing, within 100-200 views it has a strong idea and will immediately prioritize this content.
The results speak for themselves, before I started using machine learning I was getting 4 star ratings and usage was flat. Now I'm getting 5 star ratings and the app is growing.
Will it ever take off at large scale? I have no clue, but I've seen such strong benefits from the machine learning that I'm now working on developing improve.ai full time.
The difference between A/B testing and reinforcement learning is that reinforcement learning does not use a control and does not wait for high confidence to continue to improve. This allows much more data-efficient learning than A/B testing because at every step it is making its best guess as to whether to continue to explore or exploit what its already learned.
As to it having nothing to do with orchestrating code:
Most code is logic reacting to data. Reinforcement learning replaces hand-coded logic with goal-driven logic. If you can use a declarative approach to specify your goals, much of the logic can be moved to reinforcement learning.
I'd be more interested in other way of using AI to automate coding - make it to actually write code. Train it on existing code and let him figure out how to write a piece of code like a programmer would. I think it has much more potential than AI doing the calculations itself.
Interesting part is that a smart computer could resolve ambiguities in a human description of program desired in a way similar to humans. Missing part to this idea is that unless it's perfect, it would need a way to explain choices and results and probably some dialog system to iteratively improve upon how it resolved ambiguities.
E.g, make me an app like Uber but for cats -> here is a version you can play with -> oh I don't really like the cat icon, can we change it -> sure, which of these would you like ; etc etc
Computer requires ever changing human context, and maybe could have individualized context. So it has to learn over time. The point is to maximize efficiency of getting things made: how little needs to be specified before computer gives you something you accept / how fast can you go from some vague idea in your head to working acceptable software.
You should at least be able to get as good as an arbitrarily large number of people who lived a very similar life to yours and were put in a time bubble where you could talk with them to have them write software for you, assuming they're organized very well and highly motivated and great programmers and all that.
what if programming wouldn't involve defining exact steps, but instead just roughly defining what we have and what we want and maybe giving a few hints, and having the computer generally do the right thing - wouldn't that be awesome?
I experience enough frustration with things like debugging generated code, ostensibly "smart" devices which seem to "have a mind of their own" (maybe that's the point, but it's not doing what I want), and getting Google's search engine to find exactly what I want with its pseudo-AI machine-learning algorithms doing completely inexplicable things with my queries, that I think "generally do the right thing" is not a good idea. Edge cases matter a lot.
Actually Google works kind of OK now after they overshot seriously some years ago. Today if you use doublequotes around the search terms it actually seems to search for that exact term.
Which I think is a good solution: reasonable AI with easy fallback when you need it.
I guess an AI VM would need an exact modifier: don't attempt any unspecified cleverness on this variable/method/class.
Specifying some kind of runtime assertions on steroids could perhaps also alleviate some problems.
Debugging could be simplified by having the VM outputting all its assumptions.
We imagine a future where AI becomes a dominant paradigm for "writing" software -- I think that will be the case, but not in the way everyone suspects. I think 80% of the new value of software in the future will be derived from AI components, but that 80% of the production costs will still go into the structural glue code that supports the value-powerhouse models. Thus, most of the software written in the future will look similar to most of the code written today.
I also suspect that as the complexity of AI models increases, the structural code required to support these models will keep pace in complexity. For this reason, I see a future where the unit cost of high-quality software does not see any big drop, but where the value of this software continues to increase exponentially. A corollary to this is that valuable software will be no easier to program in the future than it is today.
So, Prolog?
What was supposed to be the wave of the future was the Fifth Generation Computer Project [1], initiated in Japan. Its ambition was to create machines that ran Prolog natively, as in, in special-purpose hardware. What turned out to be a "massive bust" was any attempt to use special purpose hardware in the face of rapid increases in both speed and power by general-purpose hardware (ie, x86). The same fate awaited Lisp Machines [2] and similar projects.
Prolog and generally logic programming hasn't really gone bust at any point. The point of Prolog was to use first-order logic as a computer programming language. That worked just fine, and works just fine nowadays still, although of course automated theroem proving must always rely on heuristics in order to be practical.
As to the issue of efficiency, most Prolog interpreters today are based on the Warren Abstract Machine, an efficient virtual machine for Prologs. There are other designs besides it that are also equally efficient.
Prolog has not really ever had an issue with efficiency ever since the early seventies. In fact it was a previous attempt at a "pure" logic programming language that had the efficiency issues, PLANNER [3]. Prolog was created specifically to be an efficient logic programming language, sacrificing purity for pragamatism.
I calculate it will be at least 2070 before we hear the last of it, of course.
_______
[1] https://en.wikipedia.org/wiki/Fifth_generation_computer
[2] https://en.wikipedia.org/wiki/Lisp_machine
[3] https://en.wikipedia.org/wiki/Planner_(programming_language)
But, a key problem was the runtime (in)efficiency of the prolog implementation engine. Maybe today with x1M more powerful computers it is worth trying again ?
Neural networks were abandoned in the 80s and made a massive comeback with a. more compute power b. convolutional networks
In fact, maybe a ML-optimized VM will make higher-level languages useful again ;)
Prolog's strict left-to-right, depth-first search strategy allowed the implementations to be, in fact, quite fast. But that same strategy also kept it from being more than a small step toward true declarative programming, because Prolog programmers have to understand the order in which subgoals are tried. For example, consider a goal that can be satisfied by either of two clauses, which we'll call A and B, and where every problem instance can be solved by exactly one of these; however, clause A always completes (either succeeding or failing) in constant time, but clause B, if invoked on an instance that would cause it to fail, goes into infinite recursion (an easy thing to do by accident in Prolog). It's imperative (ha!) for the Prolog programmer to make sure that clause A is tried before B.
This kind of thing comes up all the time in Prolog programming. On the one hand, you have to be aware of the order of operations so you don't cause infinite recursions (or, short of that, cause your program to take exponential time); on the other, Prolog programmers frequently exploit the left-to-right, depth-first strategy by using the operator known as the "cut". The cut is a non-logical operator in the sense that its semantics can be expressed only by reference to the Prolog search order.
Programs written in a true declarative language might superficially look a lot like Prolog programs, but the implementation would need to be much smarter -- doing things like figuring out the correct order of operations on its own. (I think machine learning might actually turn out to help with this.)
Anyway the problem with your suggestion that we just need to throw more hardware at Prolog should be evident by this point. It doesn't matter how fast your machine is if your algorithm is exponential in the typical case (never mind if it contains an infinite recursion!).
It's ... a programming language? It's Turing complete. Nobody said it's intelligent.
>> It's imperative (ha!) for the Prolog programmer to make sure that clause A is tried before B.
That is one of those cases where Prolog takes the pragmatic approach to allow efficient computation rather than sticking to "pure" semantics of the kind that tends to make a big mess of things just to keep things "clean" (like, oh, I don't know... monads?).
Btw, I've written reams and reams of Prolog in the last five or six years. The fact that your code has two readings, declarative and imperative is only a problem if you allow your mind to remain stuck in some purist definition of declarative programming that looks beautiful but doesn't really work.
If you accept that we live in an imperfect world, have to contend with primitive computers and limited resources of all kind, then Prolog is fine and miles and miles ahead of anything else in terms of declarative semantics. Even lisps have magickal and mysterious stuff like eval etc.
In actual Prolog programming practice the imperative reading means you can actually debug your code and follow it around as it falls over your own bugs. A purely declarative program would also be purely undebugable.
The dual semantics is only a problem if you don't understand the language. And in what language is that not what you'd expect?
>> Prolog programmers frequently exploit the left-to-right, depth-first strategy by using the operator known as the "cut".
No, let's say things the way they really are. The cut is there to allow a branch of the depth-first tree to be, well, cut. Correct, its semantics are purely imperative. Its real use though is to stop unnecessary searching and backtracking and therefore make your program more efficient.
It's not there to "exploit" anything. The fact that it can be exploited is troublesome, but so is all sorts of stuff in programming, like buffer overruns or sql injection. It sucks, but ... imperfect world, scarce resources etc.
>> your algorithm is exponential in the typical case
What? Why does your algorithm have to be exponential if it's in Prolog? What the hell are you on about?
But I was trying to explain why Prolog is not the declarative language that we all hope for (well, a lot of us do, anyway) and that it initially appeared, to some, to be. And I think the answer to that is exactly what I said. That doesn't mean it's not a useful tool!
> [The cut is] not there to "exploit" anything. The fact that it can be exploited is troublesome, but so is all sorts of stuff in programming, like buffer overruns or sql injection.
Whoa! "Exploit" is a general term; it doesn't just refer to security vulnerabilities. Dictionary.com offers this definition for the verb: "to utilize, especially for profit; turn to practical account: to exploit a business opportunity". (The definition I would offer is "to take advantage of", which can mean to make use of a vulnerability, but doesn't have to: you can take advantage of a convenient feature of a program.)
So when I say people "exploit" the search strategy by using the cut, I mean only that they gain benefit from it; if the search strategy were not so well-defined, the cut would be unusable.
> Why does your algorithm have to be exponential if it's in Prolog? What the hell are you on about?
If you try to write a significant Prolog program without understanding the search strategy, as if it really were a declarative language, your program will wind up being exponential or worse. Merely throwing hardware at this problem won't fix it. That's all I'm saying. I agree I didn't say it well the first time.
:P
>> Whoa! "Exploit" is a general term; it doesn't just refer to security vulnerabilities.
Of course. I didn't mean it in that sense. Buffer overruns can be exploited for non-malicious purposes also. Basically, any quirk of any language or architecture, or really any system, can be exploited for whatever purpose. Let us pause for a second and reflect on The Story of Mel [1] as handed down to us by our forefathers and mothers of old.
So what I'm saying is that the cut is there to stop unnecessary backtracking and not to change the behaviour of your program, but of course there's nothing stopping some poor fool from using it in the latter manner, as indeed I've done too many times in the past myself, being the particularly foolish fool that I am. Prolog programmers even have a term for the two types of cut: "green" and "red", respectively. Any Prolog tutorial or bit of documentation will tell you that the cut is to be used sparingly and only to stop unnecessary backtracking, not to make your program change behaviour. The good ones go to some lengths to give you examples of what happens if you don't stick to the advice. If you screw up after that you have nobody to blame but your inexperience, and that gets better with time.
So the cut is dangerous, but that's all it is.
I learned to program with C# oddly, at the University of Hull in the UK. There, our programming 101 tutor explained why C#, or, hell, Java- and not C or C++. His point was that those other languages are more powerful but because of their power they give you the tools to cut yourself to pieces. He used a metaphor involving a chainsaw, that I don't remember very well (that was back in 2005, 11 years now). But basically his point was that a chainsaw is powerful but you can really hurt yourself with it if you don't know how to use it, so you don't want to start learning ... er, forestry? with one.
Well, think of Prolog as a particularly dangerous language. I will admit this: Prolog is not your friend. It doesn't even try to make things easy for you. It's not an "easy language to pick up and start hacking in immediately". It takes a long time to learn it well and it keeps surprising you in very nasty ways for a very long time.
But- once you've learned it pays back in spades and you can do stuff in it that you can really not do in any other language, like declare grammars and then execute them, and use them to parse strings and generate strings. Or run your code backwards. Or do list appends in single-steps and so on.
Well. Apologies, that got a bit out of hand.
A program that looks at a pattern, emulates it and then enumerates the various edge-cases, looking for further patterns from the programmer's answer.
It would still require effort but it could be a lot easier than present approaches and it might even find edge-cases a human would miss.
> A program that looks at a pattern [...]
As others said the use of frameworks and even higher level scripting languages with an ide is already a dumb-ai kind of human-friendly conversation with the machine.
A problem with driving this further down the road like the article suggests could be, that if i wanted to talk to the machine like i talk with other persons, the natural language used in this case migh not be very well suited to express what i actually want. I would need special definitions and terminology, and in some cases a general description would not suffice, so the need for precision in expression might stay.
The actual dialogue with the machine then might last as along as a programmer would have needed to program it. I could see how this might work for very simple programs (like for some uber-app which is not much more than a wrapper for a telephone call to the taxi central), but inherent complexity that other programs need cannot be simplified away by switching the language to a conversational chit chat level.
People freak out every time when this idea appears and the recurring argument is that "the AI will not do the right thing, it is too stupid". They forget that our frameworks/libraries and complicated software stacks already work as dumb AIs. They follow hardcoded rules and try to please us and most of the time it actually works otherwise we would not use libraries. Using a neural network may not be the right choice for this problem but the general idea is correct. A good library should hide the "how" as much as it can and only require the user to specify the "end goal".
Like:
---
Programmer inputs on left:
compute std dev of x please
AI on right proposes edit to code:
+ import numpy as np
...
+ stddev_x = np.std(x)
---
Not super complicated to start with, but you can see where it will go from there.
>To accomplish this goal, we leverage a dataset from a pedagogical programming online judge (OJ) system,2 intended for the undergraduate course, Introduction to Computing. The OJ system comprises different programming problems. Students submit their source code to a specific problem, and the OJ system judges its validity automatically (via running).
And trained seq2seq model on it on character level and it almost works, barring a few typos. IMHO this is an underappreciated breakthrough. With more data and a better model generating competition-grade programs seems possible.
We start by replacing if/then statements with a decide() function and some goal events.
I've used this approach in my app, 7 Second Meditation, to achieve a solid 5 star rating across 248 reviews and 40% first month retention.
https://itunes.apple.com/us/app/7-second-meditation-daily/id...
I'll be writing some articles deep diving into 7 Second Meditation and breaking down how I'm achieving this results. For now, here is a taste:
https://blog.improve.ai/hi-world-how-to-write-code-that-lear...
Program synthesis is a very active field of research and many AI-based methods have been proposed in the last decades, IMHO what most systems lack is the applicability to real-world programming languages and use cases though.
Having worked on static program analysis, I know that even our current ability to understand and reason about existing programs is still very limited. A main reason for this is that most real-world systems are composed of many parts that are not easily specifiable under a single paradigm (e.g. templates, database code, configuration files).
To build a usable AI-based programming system, we will need:
* A description languge that is able to model ALL aspects of a given real-world system under a single paradigm
* A system to analyze and understand the artefacts produced by the above system
* A way to generate real-world code from the specification above, including a way to "fill in the blanks" that the user did not specify (as leaving out the details the whole point of such a system)
* A way to test the generated code against the specifications provided by the user and further "reasonable" assumptions, which will be needed as the specifications by the user will not be complete, see above
* A way to guide this process towards a reasonable program through user feedback within a reasonably small number of steps
While none of these things are impossible, implementing them is a significant challenge with a lot of unknowns for which we don't have good solutions yet.
I therefore think the first AI-based systems which we'll see in the coming years will be limited to specific problem domains (e.g. data analysis, logic programming) for which we can more easily build a system as the above.
A partial explanation is that I dont like the assumption that once work is being performed at higher and higher abstracted layers, that machine hardware, OS kernels, compilers and linkers, package and dependency managers, and all other systems software supporting high level programming paradigms (including AI based methods) are going to fall in line at the application layer.
Nope.
From my other comment (in this case the example was an amazon like shopping site):
> The thing I would like to get working is telling the net "here is a ton of different buttons, grids, lists and a lot of other UI stuff, and there are all our products - I want to maximize revenue - do whatever you like to get there".
The way of telling a neural network these things would be these few lines of code which would hook up different parts to get it working.
How is your 'project codebase markup' any different from filling in some radio buttons on a template generator or a CMS?
Better ?!
There is also the famous quote about how any working (and understood) AI is no longer considered AI...