<p>In imperative and functional languages, programs which misbehave at runtime can be debugged by setting breakpoints, stepping through the execution while observing the program state, or by using stack traces to help locate the root cause of a runtime error.</p>
<p>However, these techniques may be inapplicable in some declarative languages, particularly in the paradigms of <a href="https://en.wikipedia.org/wiki/Logic_programming" rel="noreferrer">logic programming</a>, <a href="https://en.wikipedia.org/wiki/Constraint_programming" rel="noreferrer">constraint programming</a> and <a href="https://en.wikipedia.org/wiki/Query_language" rel="noreferrer">query languages</a>. In such languages:</p>
<ul>
<li>Programs describe problems to be solved without directly describing algorithms for solving them, so the steps of execution don't correspond directly with parts of the source code, so breakpoints don't really make sense in this context.</li>
<li>Particularly when the basic unit of computation is not a function which can call other functions, the implementation's call stack will not map directly to how the program is evaluated, and each line in a stack trace doesn't necessarily correspond with an individual part of the source code.</li>
</ul>
<p>What other kinds of information or tools can such languages provide to assist with debugging of programs at runtime?</p>

<debuggers><declarative-programming>
How can declarative languages provide useful information or tools for debugging?
<p>One of the distinctive strengths of Prolog is its approach to declarative debugging, a.k.a. reversible debugging. In <a href="https://youtu.be/G_eYTctGZw8?t=768" rel="noreferrer">Production Prolog</a> (video) at Strange Loop 2014, Michael Hendricks gives a nice simple demonstration of this.</p>
<p>He begins with a function that’s supposed to tell whether a name is “short”, according to whether its length is less than 4 code points; yet it has a bug:</p>
<pre><code>?- short(hi).
false.
</code></pre>
<p>Running it with debugging enabled shows the definition of <code>short</code>:</p>
<pre><code>short(Atom) :-
    atom_codes(Atom, Codes),
    len(Codes, Len),
    Len &lt; 4.
</code></pre>
<p>For those unfamiliar with Prolog, this is equivalent to the logical expression “for all <code>Atom</code>, <code>Atom</code> is <code>short</code> if there exist some <code>Codes</code> and <code>Len</code>, such that: <code>atom_codes</code> relates <code>Atom</code> with <code>Codes</code>, and <code>len</code> relates <code>Codes</code> with <code>Len</code>, and <code>Len</code> is less than 4.”</p>
<p>He attempts to step <em>over</em> <code>len</code>, showing that <code>len</code> is what fails—but in order to know <em>why</em>, he would’ve needed to step <em>into</em> <code>len</code>. Yet he doesn’t need to restart debugging to try again, because the debugger can take advantage of the fact that Prolog already has backtracking built in. In particular, it can <em>modify</em> the backtracking stack: to say “undo step-over, instead step-in”, it can simply add a choice point above the current clause, backtrack to that, and then step in, as originally intended.</p>
<p>This leads to the definition of <code>len</code>:</p>
<pre><code>len([_|T], N) :-
    len(T, N0),
    succ(N0, N).
</code></pre>
<p>That is, the length of a list is <code>N</code> if the length of its tail <code>T</code> is <code>N0</code>, and <code>N</code> is the successor of <code>N0</code>.</p>
<p>Stepping over the clauses shows that when the input is <code>&quot;hi&quot;</code>, and thus the tail is <code>&quot;i&quot;</code>, the inner call to <code>len</code> fails; again backtracking and stepping into that call shows that the unexpected failure happens when the tail is <code>&quot;&quot;</code>, and thus the reason for the bug is clear: <code>len</code> is missing a case for the empty list. At this point, he simply edits the code to add the missing case.</p>
<pre><code>len([], 0).
</code></pre>
<p>Whereupon, he resumes stepping through the program, as if that clause had been present originally, and the updated code returns <code>true</code>.</p>
<p>Under SWI-Prolog, running the program in the debugger does disable some optimisations such as tail-calls and aggressive garbage collection of choice points. This isn’t <em>strictly required</em> for it to work, there’s just no sense in discarding that information. Really the core features are all enabled by the execution model with its pervasive backtracking; debugging events are organised based on a <a href="https://swish.swi-prolog.org/pldoc/man?section=debugoverview" rel="noreferrer">state machine model</a> on top of that.</p>
<p>So adding another clause to <code>len</code> while the execution point is <em>within</em> <code>len</code> is effectively just adding another possible branch to the parent frame in the call stack. The key to all of this is the guarantee that failure <em>always</em> attempts to backtrack, so the system can implement quite sophisticated debugging features while only needing to make local modifications to the call stack; and the fact that, by default, data structures are immutable and persistent.</p>
<p>In the same talk, Michael goes on to mention <a href="https://mercurylang.org/" rel="noreferrer">Mercury</a>, a functional logic language which uses this availability of the call stack to great effect: the debugger itself can behave like a logic program, whose goal is to <a href="https://mercurylang.org/information/doc-release/mercury_user_guide/Search-modes.html#Search-modes" rel="noreferrer">search</a> for a bug, with the help of the programmer as an <a href="https://mercurylang.org/information/doc-release/mercury_user_guide/Oracle-questions.html#Oracle-questions" rel="noreferrer">oracle</a> to say which parts are right or wrong, trusted or suspicious.</p>
<p>Whereas <a href="https://jakob.engbloms.se/archives/1547" rel="noreferrer">reversible debugging for imperative languages</a> (e.g. in GDB or Mozilla’s RR) is typically more costly and less reliable, because it tries to be non-intrusive while dealing with pervasive mutation. The most widespread technique is based on <em>recording</em> the execution state of the program incrementally or at various checkpoints and <em>replaying</em> it to reach the desired point.</p>
<p>The general principles of declarative debugging are applicable to other languages, though. If you define a core language and an abstract machine semantics (e.g. a <a href="https://en.wikipedia.org/wiki/CEK_Machine" rel="noreferrer">CEK Machine</a>), then in some sense the “natural” debugger is like Prolog’s state-machine model, allowing breakpoints on any state transition. It’s useful to translate an abstract machine into a simple, inefficient model implementation of a language anyway, both in the interest of building something quickly, and so that you have a reference for optimisation purposes; and if you plan ahead just enough to make it runnable step-by-step, then you get a very basic debugger automatically.</p>
<p>Finally, a dynamic debugger can also be made <em>less needed</em> through other features. In a language like Haskell, referential transparency means that I can reason about programs equationally, so I can often debug purely by simple algebra, which doesn’t require any runtime support—or even a computer!</p>

CC BY-SA 4.0
2023-05-24T21:11:11.153Z
2023-05-24T21:11:11.153Z
Jon Purdy
# How can declarative languages provide useful information or tools for debugging?
Posted by: username_0 on 2023-05-24
In imperative and functional languages, programs which misbehave at runtime can be debugged by setting breakpoints, stepping through the execution while observing the program state, or by using stack traces to help locate the root cause of a runtime error.

However, these techniques may be inapplicable in some declarative languages, particularly in the paradigms of [logic programming](https://en.wikipedia.org/wiki/Logic_programming), [constraint programming](https://en.wikipedia.org/wiki/Constraint_programming) and [query languages](https://en.wikipedia.org/wiki/Query_language). In such languages:

* Programs describe problems to be solved without directly describing algorithms for solving them, so the steps of execution don't correspond directly with parts of the source code, so breakpoints don't really make sense in this context.
* Particularly when the basic unit of computation is not a function which can call other functions, the implementation's call stack will not map directly to how the program is evaluated, and each line in a stack trace doesn't necessarily correspond with an individual part of the source code.

What other kinds of information or tools can such languages provide to assist with debugging of programs at runtime?
**Tags:** debuggers declarative-programming
---
## 1 answers
### Answer by username_1 on 2023-05-24. Score: 6 | Accepted answer
One of the distinctive strengths of Prolog is its approach to declarative debugging, a.k.a. reversible debugging. In Production Prolog (video) at Strange Loop 2014, Michael Hendricks gives a nice simple demonstration of this.
He begins with a function that’s supposed to tell whether a name is “short”, according to whether its length is less than 4 code points; yet it has a bug:
?- short(hi).
false.

Running it with debugging enabled shows the definition of short:
short(Atom) :-
    atom_codes(Atom, Codes),
    len(Codes, Len),
    Len < 4.

For those unfamiliar with Prolog, this is equivalent to the logical expression “for all Atom, Atom is short if there exist some Codes and Len, such that: atom_codes relates Atom with Codes, and len relates Codes with Len, and Len is less than 4.”
He attempts to step over len, showing that len is what fails—but in order to know why, he would’ve needed to step into len. Yet he doesn’t need to restart debugging to try again, because the debugger can take advantage of the fact that Prolog already has backtracking built in. In particular, it can modify the backtracking stack: to say “undo step-over, instead step-in”, it can simply add a choice point above the current clause, backtrack to that, and then step in, as originally intended.
This leads to the definition of len:
len([_|T], N) :-
    len(T, N0),
    succ(N0, N).

That is, the length of a list is N if the length of its tail T is N0, and N is the successor of N0.
Stepping over the clauses shows that when the input is "hi", and thus the tail is "i", the inner call to len fails; again backtracking and stepping into that call shows that the unexpected failure happens when the tail is "", and thus the reason for the bug is clear: len is missing a case for the empty list. At this point, he simply edits the code to add the missing case.
len([], 0).

Whereupon, he resumes stepping through the program, as if that clause had been present originally, and the updated code returns true.
Under SWI-Prolog, running the program in the debugger does disable some optimisations such as tail-calls and aggressive garbage collection of choice points. This isn’t strictly required for it to work, there’s just no sense in discarding that information. Really the core features are all enabled by the execution model with its pervasive backtracking; debugging events are organised based on a state machine model on top of that.
So adding another clause to len while the execution point is within len is effectively just adding another possible branch to the parent frame in the call stack. The key to all of this is the guarantee that failure always attempts to backtrack, so the system can implement quite sophisticated debugging features while only needing to make local modifications to the call stack; and the fact that, by default, data structures are immutable and persistent.
In the same talk, Michael goes on to mention Mercury, a functional logic language which uses this availability of the call stack to great effect: the debugger itself can behave like a logic program, whose goal is to search for a bug, with the help of the programmer as an oracle to say which parts are right or wrong, trusted or suspicious.
Whereas reversible debugging for imperative languages (e.g. in GDB or Mozilla’s RR) is typically more costly and less reliable, because it tries to be non-intrusive while dealing with pervasive mutation. The most widespread technique is based on recording the execution state of the program incrementally or at various checkpoints and replaying it to reach the desired point.
The general principles of declarative debugging are applicable to other languages, though. If you define a core language and an abstract machine semantics (e.g. a CEK Machine), then in some sense the “natural” debugger is like Prolog’s state-machine model, allowing breakpoints on any state transition. It’s useful to translate an abstract machine into a simple, inefficient model implementation of a language anyway, both in the interest of building something quickly, and so that you have a reference for optimisation purposes; and if you plan ahead just enough to make it runnable step-by-step, then you get a very basic debugger automatically.
Finally, a dynamic debugger can also be made less needed through other features. In a language like Haskell, referential transparency means that I can reason about programs equationally, so I can often debug purely by simple algebra, which doesn’t require any runtime support—or even a computer!
---
