7 ms·
Barliman: Prototype of a smart text editor
- sdegutis 10y agoSo, this is a text editor primarily for scheme, with a GUI for TDD built in?
- chrismonsanto 10y agoIt is an interactive program synthesizer, as it says in the overview
- will_byrd 10y agoYes, it's a prototype editor with interactive example-based synthesis. Barliman's synthesis can try to fill in "missing" sub-expressions in a Scheme definition. However, there is also a TDD component that might not be obvious. Barliman will attempt to run each test individually, even if the function has not been fully defined. That is, Barliman will attempt to synthesis a definition of the function to make each test pass. If Barliman can prove that there there is no way to fill in the function definition to make the test pass, the test will display an error message. In other words, Barliman runs unit tests continually, and those tests can fail before you have finished defining the function being tested. Hopefully this feedback will let the programmer know that they are heading down the wrong path as soon as possible. Or, let the programmer double check the test, to make sure the test is correct.
- cheez 10y agoIt wasn't clear to me how the "best guess" works. Did I miss it? Indeed, if program synthesis can be done for even slightly non-trivial tasks (find in list, etc) that would be a huge boon for StackOverflow answer bots.
- will_byrd 10y agoI gave a short, semi-technical explanation of how Barliman performs synthesis in my answer to `YeGoblynQueenne`. I'm not sure if that description answers your question, though. I agree that relatively modest synthesis could be useful; exploring modest synthesis is why I made Barliman, although I hope Barliman's synthesis can be made less modest! :)
- gbersac 10y agoThis is ambitious. I don't really believe it will be rally useful one day, but who know, maybe it is the primitive form of a program which will replace programmers in the future.
- will_byrd 10y agoThanks! Yes, Barliman is ambitious. Both the synthesis capabilities and the interface will need to improve before Barliman might be useful for practicing programmers. One question Barliman is trying to explore is whether relatively modest synthesis abilities might be useful for some tasks. If the last 10% of a function could be synthesized, for example, how useful would that be? Perhaps a better question is, "for which tasks, if any, would modest synthesis be useful"? I don't know the answer to this question. A tool like Barliman might be useful in an educational setting. However, this seems a bit like the calcular/Wolfram Alpha debate in teaching math. If Barliman becomes good enough to synthesize many simple Scheme definitions from examples, would that take away too many learning opportunities from students? I suppose it would teach students to think of example tests, and perhaps even properties, types, or contracts, for the functions they are defining. But it does seem that the better synthesis works, the less useful Barliman might be in a teaching setting. One suggestion from Matt Matt is to use Barliman for code repair. For example, say I define a function `foo`, along with several tests that `foo` passes. Later I find that the definition of `foo` is incorrect, and come up with several more tests that fail using the current definition. Barliman could have an "auto repair" button that attempts to synthesize a correct definition of `foo` from both the tests and the "almost correct" existing definition. I have several ideas of how this might be done. For autorepair (and other synthesis tasks) it would be helpful to extend Barliman to run synthesis tasks remotely--for example, on an EC2 X1 instance with dozens of hardware threads. For more advanced synthesis tasks, I think we'll need a more sophisticated search. I was very impressed with Alpha Go's performance over a giant search space that historically has been considered the domain of human experts, a task that reminds me greatly of synthesis. I'm working with Rob Zinkov and Evan Donahue on using stochastic search/Markov Chain Monte Carlo/etc. to try to allow miniKanren's search to explore more promising areas in the search space. One inspiring piece of related work is this 2013 ASPLOS paper by Schkufza, Sharma, and Aiken on Stochastic Superoptimization: http://theory.stanford.edu/~aiken/publications/papers/asplos13.pdf http://theory.stanford.edu/~aiken/publications/papers/asplos... I don't see Barliman or other synthesis tools replacing programmers any time soon, but in 10 or 15 years I hope our tools will be assisting us with useful synthesis tasks.
- runeks 10y ago> given a fully or mostly-specified definition of some function foo, Barliman will attempt to prove that a partially-specified test is consistent with, or inconsistent with, the definition of foo. I feel like this is what GHC (the Haskell compiler) does for me. Where the "test", in this case, is the type definition. And there is no room for error here. So it's possible that this idea makes more sense for languages without a strong type system. In any case, trying to complete a partial function definition without looking at the native types of the language means you miss a lot of information, especially in the case of Haskell, where the types tell you so much, if not everything, you need to know about a function.
- Cybiote 10y agoI don't think that is quite right. This says it's applying basic ideas from program synthesis, which is not too distant from automated theorem proving style AI (specially when you get to SMT solver based synthesis). From skimming the page, it looks to me like an example of inductive programming. So for Haskell, it would be closer to something like Djinn, where code is generated/proved from a type specification.
- runeks 10y ago> So for Haskell, it would be closer to something like Djinn, > where code is generated/proved from a type specification. I don't understand. How is this generating/proving different, in essence, from GHC generating machine code from Haskell? What do we gain by having Djinn generate the Haskell code, rather than writing the Haskell ourselves?
- will_byrd 10y agoHopefully my answer above makes this more clear. The high-level idea is that if you are going to take the trouble to specify the type of a function (as in Haskell), and tests that use the function (as in unit testing), and high-level properties of the function (as in Quickcheck), you may as well try to get the computer to actually generate the function for you, rather than writing it yourself. You mentioned Coq above. Coq users rely on the `crush` tactic to try to fill in the boring details of a proof obligation. This is similar in spirit to search used in synthesis systems. If you can give the high-level specification, let the computer do the "boring" work. Of course, the boring work may be difficult or computationally expensive, and the high-level specification may be ambiguous...
- fspeech 10y agoByrd has been working on miniKanren for over a decade. He showed before how you can easily program miniKanren to produce quines through search. The question I would have is that producing specifications for trivial tasks may be just as hard if not harder than programming the same tasks. Often the program is the specification.
- lopatin 10y agoAgreed, because the problem domain/system dynamics needs to be encoded into Scheme before synthesis can be useful for high level specs. If this kind of programming style takes off, it could possibly be useful for communities to supply "starter templates" for common patterns and system behaviors that they manually reason about all the time.
- runeks 10y agoSo is this like a simpler interface for making Coq-like specifications?
- will_byrd 10y agoYes, using templates for common patterns could be helpful. Or even using machine learning over existing code bases to infer such templates. Similar to the use of templates is Matt Might's suggestion of using Barliman for code repair--given an almost correct definition of a function, and both passing and failing tests, try to massage the code to make it pass all the tests. I think templates could be useful here. There are many approaches to synthesis, and Barliman's implementation is still very naive. Experiments by Michael Ballantyne and Greg Rosenblatt have shown that some synthesis tasks in miniKanren (used internally by Barliman) can be speed up by factors of thousands to millions (by restricting the grammar and using a type system, or by performing program specialization on the relational Scheme interpreter, as in the Mercury compiler). Alas, since synthesis is inherently exponential in terms of program size, a speedup of a million means that you can synthesize only a slightly larger expression. And the techniques Michael and Greg have used don't work for all problems, and can reduce the generality of the programs that can be synthesized. Still, given how many synthesis techinques, tricks, and optimizations that we haven't tried, I'm optimistic that Barliman's synthesis can be improved enough to be practical for at least some uses. What those uses are, I'm not sure.
- YeGoblynQueenne 10y agoIt would have been nice to see some more information on the way this works. I'm not clear exactly what is being searched- some set of built-in functions that are combined in the hopes of finding one that makes tests pass? A space of function components? It's cool but I'd like to know what it does exactly. Maybe the explanation is spread around examples, but skimming through them I couldn't find it.
- will_byrd 10y agoBarliman's synthesis is based on the "relational interpreter" approach described in this 2012 Scheme Workshop paper: William E. Byrd, Eric Holk, and Daniel P. Friedman. miniKanren, Live and Untagged: Quine Generation via Relational Interpreters (Programming Pearl). Proceedings of the 2012 Workshop on Scheme and Functional Programming, Copenhagen, Denmark, 2012. http://webyrd.net/quines/quines.pdf http://webyrd.net/quines/quines.pdf https://github.com/webyrd/2012-scheme-workshop-quines-paper-code https://github.com/webyrd/2012-scheme-workshop-quines-paper-... The basic idea is to write an interpreter as a relation in a constraint logic programming language (miniKanren, in this case). Since the interpreter is a relation, there is no real distinction between "input" arguments and "output" values. More generally, arguments to the relational interpreter can be partially-instantiated terms that contain logic variables representing unknown subexpressions. Since the interpreter for "miniScheme" is fully relational, running the interpreter "forwards" to generate a value from a given expressions, or running the interpreter "backwards" to generate an expression that evaluates to a given value, are essentially the same operation. The only difference is where the logic variables are placed in the query to the relational interpreter. But the approach is more general than just running the interpreter forward or backward. Logic variables can be used in both the expression to be evaluated, and in the expected value. This is how we can generate quines (expressions that evaluate to themselves) in miniKanren directly from the mathematical definition of a quine, for example. The query (run N (q) (evalo q q)) will produce N quines, including a quine that is alpha-equivalent to the canonical Scheme quine ((lambda (x) (list x (list (quote quote) x))) (quote (lambda (x) (list x (list (quote quote) x))))) This example shows some of the generality of the relational interpreter approach---program inversion applied to a Scheme interpreter would not be able to generate quines. The search is done over all possible terms in "miniScheme," a Turing-complete subset of Scheme that supports higher-order variadic functions, recursion, lists and pairs, lexical scoping/shadowing, etc., and that has been extended with pattern-matching. Does that help?
- tedmiston 10y agoDoes anyone generate tests automatically? I've been looking for something related to this. Whenever I design unit test cases, I write out the common edge cases, let's say: valid input, invalid input (wrong data type), invalid input (too long), etc, then translate them into tests. I might write them in a way that the tests are the combination of various dimensions of input, one per variable. For example, try input1=['a', 'aaa', None] x input2=[-1, 0, 1, None] for each combination knowing which I expect to pass and fail. Often the tests are similar (write one, duplicate, slightly change the logic), and I've always felt like there has to be some kind of test generation framework out there to do this, though I haven't heard of anyone actually using one.
- joshschreuder 10y agoI haven't used it (I think Microsoft has abandoned the project anyway), but I think this was one of the goals of Pex (https://www.microsoft.com/en-us/research/project/pex-and-moles-isolation-and-white-box-unit-testing-for-net/ https://www.microsoft.com/en-us/research/project/pex-and-mol...) Looks like it became Intellitest (https://www.visualstudio.com/news/vs2015-vs#Testing https://www.visualstudio.com/news/vs2015-vs#Testing). But I'm not convinced such high test coverage is useful in most scenarios.
- bryanh 10y agoImmediately QuickCheck comes to mind (https://hackage.haskell.org/package/QuickCheck https://hackage.haskell.org/package/QuickCheck). Folks have written (possibly less powerful) implementations in Python (https://github.com/HypothesisWorks/hypothesis-python https://github.com/HypothesisWorks/hypothesis-python), Javascript (https://github.com/jsverify/jsverify https://github.com/jsverify/jsverify), etc. FWIW I've found them fragile and lacking for my use cases - but I bet fuzzing style testing tools could be pretty valuable in certain cases.
- will_byrd 10y agoThank you for the interest in Barliman! I'll try to answer all of the questions this afternoon. Also, I'm very much open to collaboration on Barliman, synthesis, relational interpreters/type inferencers, constraint logic programming, etc.! :)
- will_byrd 10y agoOne more high-level comment. I'm thinking of starting a series of Google Hangouts to explain how Barliman works, and more importantly, to collaborate on making the underlying technology better and explore alternative interfaces. This would build upon 40 hours of hangouts I did on miniKanren and relational interpreters in 2014 and 2015: https://www.youtube.com/playlist?list=PLO4TbomOdn2cks2n5PvifialL8kQwt0aW https://www.youtube.com/playlist?list=PLO4TbomOdn2cks2n5Pvif... The new hangouts would be more focused on research and development, trying to make Barliman more practical, and would hopefully lead to academic publications. In addition to my interest in logic programming, I'm very interested in how to work with people online to do research and writing. If this sounds interesting to you, please sign up to the miniKanren uncourse mailing list: https://groups.google.com/forum/#!forum/minikanren-uncourse https://groups.google.com/forum/#!forum/minikanren-uncourse or contact me directly: webyrd@gmail.com https://twitter.com/webyrd https://twitter.com/webyrd Thanks! --Will
- monorailz 10y agoWhat will the expected level of prerequisite knowledge be for participating in the hangout?
- will_byrd 10y agoGood question! Since I imagine hangouts based on improving/exploring/experimenting with Barliman, or other similar tools, knowledge of interface design, GUI programming, parallel programming, EC2, etc., should be just as useful as knowledge of logic programming, interpreters, type systems, etc. I think interest, creativity, and a willingness to learn is the only real prerequisite. For more technical aspects of synthesis using relational interpreters, or whatever, I'll probably do a recap of the core areas of the previous hangout series. I'm sure those 40 hours could be boiled down to something much, much shorter.
- SwellJoe 10y agoSort of a nitpick, but green always makes me think "tests passing", whereas you've got it meaning "incomplete expression" (or something along those lines, since you point out that it's not the same as syntax errors).
- will_byrd 10y agoThanks for the comment! I agree! The newer interface includes an "Illegal sexpression" messages, but still uses the sickly green color. I need to fix this--any suggestions? :)
- kragen 10y agoA wavy red underline is the established default for inline error reporting at this point, for better or worse. That's probably the best thing to use unless you're determined to make advances in graphical user interface layout, which — I hope it isn't rude to point out — doesn't seem to be a goal of Barliman, from looking at the screenshots. If you're going to highlight errors with an error background color, I suggest blue, which contrasts better with green than red or yellow can, especially if you're somewhat red-green colorblind, like I am. Alternatively, maybe you could reduce the contrast on the whole pane except for the error, as if you were trying to scam the programmer into supplying their email address to continue reading an article.
- will_byrd 10y agoGood point! I like the idea of using a wavy red line. Thanks! Yeah the user interface is pretty budget right now. :) I've been teaching myself Swift and Cocoa programming, and still have lots to learn. And I've been concentrating more on the "under the hood" pieces of Barliman. But I do want to explore new interface and GUI ideas. I suspect the interface will change completely in the future. Tom Gilray, for example, has suggested using just a regular editor window, which Barliman would parse to find the definitions, examples, optional type annotations, etc. This would be closer in spirit to the XCode interface. One interface question is how to best specify the semantics for the language under interpretation (for example, "miniScheme"). Currently the semantics are specified by writing a "relational" interpreter in miniKanren. This is pretty low level, though. I'd like to have a much high-level specification language that looks closer to the math for operational semantics.
- lake99 10y ago> I'm starting with cocoa since I'm developing on a Mac Does anyone here have an idea of how easy or difficult it would be to build this on Linux? The GNUStep website says they framework closely follows Apple's Cocoa. And yet, I am not familiar with any sizeable Mac app getting ported to Linux via GNUStep.
- will_byrd 10y agoGood question! I'm not sure how easy it would be to compile Barliman under GNUStep. I would like to have a version of Barliman that runs on different platforms, perhaps using JavaScript/Clojurescript/whatever. The GUI part of Barliman isn't that sophisticated. I think the trickier part is managing the Chez Scheme processes that are being launched/killed in the background. If there are N tests/examples, Barliman will launch N+2 processes of Chez Scheme, in parallel, each one running a miniKanren query. Killing these processes and starting new ones reliably is critical. I'm not sure how easy it would be to launch and manage Chez Scheme instances using Node.js, for example. If you are interested in compiling Barliman under GNUStep, I'd be happy to help. I'd be willing to try to rewrite parts of the code that aren't supported by GNUStep, for example. I assume GNUStep supports Swift? If not, we would have to rewrite Barliman in Objective-C, which would be fine by me. I should mention that I've been thinking about separating the GUI completely from process management, to make it easier to run synthesis processes on remote machines, such as a beefy EC2 X1 instance. At that point, hopefully it would be quite simple to write a new front end for Barliman. Do you have any recommendations for cross-platform GUIs that can also launch and manage parallel processes well? Thanks!
- lake99 10y ago> If you are interested in compiling Barliman under GNUStep, I'd be happy to help. Thank you for being open to it, but since I'm not a Schemer (yet) so I don't see myself using it, beyond playing with it for fun. > I assume GNUStep supports Swift? From the best I could gather[1], this appears to be work-in-progress. GNUStep's Objective-C API is apparently at OSX-10.6 level. > recommendations for cross-platform GUIs that can also launch and manage parallel processes well QT comes to mind. Their QProcess class seems pretty neat to me. [1] https://www.reddit.com/r/swift/comments/49r82f/swiftgnustep_support_on_linux/ https://www.reddit.com/r/swift/comments/49r82f/swiftgnustep_... [2] https://doc.qt.io/qt-5/qprocess.html https://doc.qt.io/qt-5/qprocess.html
- YeGoblynQueenne 10y agoIt's nice to see a logic programming subject on HN's first page- the second in two days.
- will_byrd 10y agoCool! What was the other post?
- YeGoblynQueenne 10y agoThis one: https://news.ycombinator.com/item?id=12193694 https://news.ycombinator.com/item?id=12193694
- will_byrd 10y agoVery nice! Thanks. You might be interested in this paper and code on the implementation of microKanren, a minimal implementation of core miniKanren. The core implementation is under 50 lines of Scheme code. Jason Hemann and Daniel P. Friedman. microKanren: A Minimal Functional Core for Relational Programming. In Proceedings of the 2013 Workshop on Scheme and Functional Programming (Scheme '13), Alexandria, VA, 2013. http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf https://github.com/jasonhemann/microKanren https://github.com/jasonhemann/microKanren