4 ms·
I've felt for awhile that it's a matter of time before we end up with a development environment that - given a collection of tests - will automatically generate
by yellowapple 9y ago
I've felt for awhile that it's a matter of time before we end up with a development environment that - given a collection of tests - will automatically generate a program which passes all the tests. Barliman looks like a really cool step in that direction, even with its stated limitations.
- setr 9y agoisn't that called prolog
- agumonkey 9y agoI wonder how far they went with prolog. I remember examples in books talking about solving a problem and outputing a plan. But it wasn't a program, not in the sense of nested/modular systems, more like a linear walk. That said, webyrd has shown kanren embedded lambda calc (evalo relation) to find which program would be reduced to some value..
- tree_of_item 9y agoNo, Prolog is nothing like that. Prolog is perhaps the sort of paradigm that could be used as one part of an implementation of something like that (as we see here with miniKanren), but Prolog itself isn't even close.
- abecedarius 9y agoProlog can (sometimes) "reverse execute" a specification, not generalize from examples. It's like saying "a cat has a round face and pointy ears" versus "look at these cat pictures". (Versus "draw an oval and then draw two triangles at the top...")
- mycl 9y agoBut generalising from examples has been a research topic in the Prolog community since at least the early 80s. The field is called inductive logic programming (https://en.wikipedia.org/wiki/Inductive_logic_programming https://en.wikipedia.org/wiki/Inductive_logic_programming).
- taneq 9y agoFor some reason the first thing that popped into my head when I read this was fuzzers like American Fuzzy Lopp. I wonder if you could use the same sort of stochastic exploration to explore the space of possible programs satisfying a set of tests rather than explore the space of possible inputs given a program?
- hanbura 9y agoI can't Google the name right now, but this does exist as an optimization technique. Just start with any program, create random permutations, score them for correctness and performance, keep the best ones, repeat. The problem is that this is incredibly computation intense, since the number of possible programs is huge. Right now it's viable for improving small code parts with a know-correct starting point. Maybe some day computers become fast enough to make more viable.
- maemre 9y agoStochastic optimization? STOKE [1] from Stanford is trying to that if I understood it correctly. [1]: https://github.com/StanfordPL/stoke https://github.com/StanfordPL/stoke
- maemre 9y agoThat's called program synthesis which is a hot research area. Specifically, what you mention is called "programming by example". I can't remember many examples on top of my head but some people from Microsoft Research are working on it for example: https://microsoft.github.io/prose/ https://microsoft.github.io/prose/
- ako 9y agoSounds like training a neural network with some test data? Software 2.0 as outlined here: https://medium.com/@karpathy/software-2-0-a64152b37c35 https://medium.com/@karpathy/software-2-0-a64152b37c35
- Sean1708 9y agoMore generally it's just an optimisation (the mathematical kind) where your parameters are essentially a function body. In that article the function body is a neural network, but there's no reason it has to be.
- vidarh 9y agoGenetic Programming is a generalization of that. The "collection of tests" is effectively the fitness function. The challenge is that 1) doing it for non-trivial functions and getting results faster than much simpler generative methods that depends on heuristics is a really hard problem (but can work better when we don't have reasonable heuristics); 2) writing exhaustive tests for a lot of the problems we care about is likely to take more effort than writing the code in the first place. I think if you want something like this the effort is best expended on tools that help you create a consistent, concise and exhaustive model / test-suite rather than code to implement it, with a focus on making it possible for a human to read and sanity check the generated model. In this case, the tool is basically trying to create a model that matches the tests, it's just that it never makes the model explicit other than in the form of finished code, which prevents us from verifying that the model is correct other than by inspecting the code and/or expanding the tests. For small functions that might be helpful, but for larger pieces of code, I think it is likely that generating the code directly is likely to lead to code that is near impenetrable and impossible to validate expanding the test suite. E.g. a recurring problem of research in genetic programming has been that a lot of the resulting solutions are hard to understand even very small/simple algorithms. And for bigger problems it's not unusual to end up exposing weaknesses of the fitness function rather than solving the intended problem. It's still an interesting project. I just think we're really far from having something with wider appeal.
- maxxxxx 9y agoIt would be fun to expand this to a full app with UI and database.