Algorithmic program debugging

What Hacker News says

1. triskaMar 2019
   In my opinion, this is true for some main points, but definitely not for all of them.

   A key difference between the languages is in how easily you can reason about programs. In Prolog, if you program in the pure monotonic subset of the language, you get certain algebraic guarantees that are not available in Lisp. For instance, for pure Prolog code and a declarative reading, removing a goal can at most increase the set of solutions, and removing a clause can at most decrease the set of solutions.

   In Prolog, these guarantees can be used to test and debug your programs by logical reasoning. In fact, to a significant extent, you can even automate debugging due to these properties. Such techniques were pionereed by Ehud Shapiro in his 1982 PhD thesis, Algorithmic Program Debugging:

   http://cpsc.yale.edu/sites/default/files/files/tr237.pdf

   The thesis is an excellent read, and I highly recommend it! Specifically, quoting from page 155:

   “Although Lisp is considered a high level language, it is not clear that it encourages precision and clarity of thought. As one Lisp hacker puts it [91]: "Lisp...is like a ball of mud. You can add any amount of mud to it...and it still looks like a ball of mud!". This aspect of Lisp is the hacker's delight, but the theoretician's nightmare. It is known that one may implement without too much effort a reasonable Prolog in Lisp. However, the issue is not implementation — the issue is the method of thought. Based on my experience with both languages I maintain that one's thoughts are better organized, and one's solutions are clearer and more concise, if one thinks in Prolog rather than in Lisp.”

   Another key feature of Prolog is that constraints blend in seamlessly, leading to an important declarative programming paradigm called constraint logic programming (CLP). This is the key reason why Prolog is frequently used to solve combinatorial tasks in practice, and often an important motivation for buying a commercial Prolog system.

   Show morethread
2. zmonxOct 2017
   This is indeed an extremely interesting approach.

   It was pioneered in the context of logic programming and Prolog by Ehud Shapiro in his 1982 PhD thesis "Algorithmic Program Debugging". The thesis was published as an ACM Distinguished Dissertation by MIT press and is available online from:

   http://cpsc.yale.edu/sites/default/files/files/tr237.pdf

   Together with Leon Sterling, Ehud Shapiro later wrote a very important introductory Prolog book called "The Art of Prolog".

   Show morethread
3. YeGoblynQueenneFeb 2022
   Possibly interesting trivium: automated debugging was first described in 1982, in Ehud Shapiro's PhD thesis titled "Algorithmic Program Debugging" (it's what it sounds like and it can also generate programs by "correcting" an empty program):

   https://en.wikipedia.org/wiki/Algorithmic_program_debugging

   Of course all this targeted only Prolog programs so it's not well-known at all.

   thread
4. YeGoblynQueenneMay 2020
   >> It would be nice to have an AI that could [write unit tests, or] look over your code and understand and explain where you might have bugs.

   What you're describing (outside of the square braces) is algorithmic debugging:

   https://en.wikipedia.org/wiki/Algorithmic_program_debugging

   It was introduced in the PhD thesis of Ehud Shapiro. There's been a steady trickle of research work since then but it's never formed into a strong current, if I may. One reason for that is of course that Shapiro's thesis was published in 1983. So it's one of the research directions that was cut short by the last AI winter. Lessons to be learned.

   Shapiro's thesis is one of two doctoral theses that became the precursors to Inductive Logic Programming, a field at the intersection of logic programming and machine learning. ILP algorithms learn programs from examples and "background knowledge" (i.e. a library of existing programs used as building blocks for new, learned programs).

   The way that algorithmic debugging works is that it finds differences between the intended "model" (in logical terms: the consequences) of a program and its actual model. An algorithm that can do that can also walk back up the AST of a program the other way and produce a correct program from examples of its intended inputs and outputs.

   That's the kind of stuff I study. Hence my comment above about lack of innovation etc. It's possible to automatically create novel programs with complex structures (recursion and invented sub-programs) and even discover new algorithms in the process and so on -and we know ways to do that right now. But the way to do it is not with a language model trained to predict the next character in a sequence.

   As to writing unit tests, the way that most ILP algorithms work is that you give them a set of examples of the inputs and outputs of the program you want to write (e.g. "droplast([alice,and,bob,sitting,on,the,tree], [alice,and,bob,sitting,on,the])") and they write the program for you. I like to think of it as a kind of automatic TDD.

   Show morethread
5. triskaMay 2018
   I can confirm this impression. In my opinion, there are several reasons for this:

   First, many types of mistakes that are common when working with lower-level languages cannot occur at all when you use a declarative language. For example, with a logic programming language, you cannot accidentally double-free a pointer or write into unintended portions of memory.

   Second, when working with a high-level language, the code is much shorter than if you had used a lower-level language. This makes it easier to debug, and also easier to get right already in the first few tries.

   Third, once there is a mistake, it can be found in ways that fit the overall paradigm nicely. For example, in pure Prolog, if your predicate terminates and has a mistake, then it is either too specific or too general (or both), and you can debug both cases very systematically and even automatically, using built-in mechanisms of the language.

   Declarative debugging methods for Prolog were pioneered by Ehud Shapiro in his 1982 PhD thesis, Algorithmic Program Debugging:

   https://cpsc.yale.edu/sites/default/files/files/tr237.pdf

   I also highly recommend Ulrich Neumerkel's teleteaching environment GUPU for systematically finding mistakes in Prolog programs:

   https://www.complang.tuwien.ac.at/ulrich/gupu/

   Show morethread
6. myclDec 2017
   The induction of logic programs in Prolog from examples was done by Ehud Shapiro's "Model Inference System" described in his PhD thesis, "Algorithmic Programming Debugging" (https://www.amazon.com/Algorithmic-Program-Debugging-Disting...), in 1982.

   This was one of the earliest inductive logic programming (https://en.wikipedia.org/wiki/Inductive_logic_programming) systems.

   thread