Debugger / explorer - plan

[atacratic]

This issue tracks the overall plan and progress on implementing the unison explorer.

Here are links to the key posts from the trail below.

• Sketch spec
• Plan

---- [original text follows] ----

I've been playing with an idea for a debugger (or 'explorer') for Unison, and wanted a place to post it for discussion.

Feel free anyone to post reactions or other ideas!

Don't expect this to get much attention from the core team anytime soon though - this would be a major project, and there are already a few of those on the go. Maybe this is something for another year!

Post to follow, below...

[aryairani]

Looking forward to it.

[atacratic]

Wouldn't it be great if Unison let you really see what your code is doing? So it feels like you're holding the code in your hands and watching it run? Rather than how it is with trace statements and the REPL - which feel more like taking measurements about your code from behind a lead-lined screen.

Outline of this post...

• What debugging tools do we have today, and what's wrong with them?
• What properties do we want from a debugging tool?
• A proposal for a Unison console-based debugger
  • sketched out by example, with mocked-up screenshots
  • various comments
• A few notes of comparison with other tools.

What tools do we have today?

What tools do we have for understanding why a program produces the result it does? Here are the ones that are commonly used with functional code.

• Add printf / Debug.trace, either
  • ad hoc - instrument your code as a one-off, to understand a specific bug, or
  • systematically add logging of the control flow to file, to help with bugs you might hit later.
• Write REPL/watch expressions to match what you think is happening inside your program.
• Things like ghci's debugger, which lets you step expressions forward to see intermediate results, and set breakpoints in order to focus on the values of expressions at a specific line of code.

These have some major shortcomings.

• Adding trace statements is slow and repetitive, and only gives you small morsels of information. The stream of text output you end up with is difficult to correlate to different stages of the program's execution.
• Systematic logging of everything adds visual noise to the code, and requires up-front investment and machinery. And it doesn't help you when you call library code which lacks the logging.
• REPLs are good, and watch expressions are great: but it's pretty hard work to figure out what expressions you need to watch, to get an insight into your program. If the problematic code is 10 stack levels deep, then that's a lot of layers of function calls you need to track through, figuring out the arguments at each stage.
• A debugger like ghci's is powerful, but has two big problems:
  • You can't see the code. Or even if you can dump a code listing, it's hard to correlate the execution results you're seeing to the code that produced it. If you've got a graphical IDE with debugger (come back VisualBasic 6, all is forgiven!) then you're doing pretty well here. Which functional languages have one of those?
  • The work you do to navigate the code and the execution flow in the debugger gets wasted, in the same way as work you do to set up your REPL session is wasted. You can't get it back again easily if you want to rerun, or after you've changed your code.

What do we want instead?

What we want is a way of just seeing what your code is doing, in a live, hands-on way. We want our environment for exploring code execution to have the following properties.

• [overlayed results] You see calculated values in situ, overlayed on or close to, the code that produces them.
• [exploring the code] You can drill down into the code the same way you navigate code in your editor - from one function, down into the functions it calls, and back up again.
• [persistent] Once you've done the work of finding part of the code, or a stage of the execution, that looks interesting, you can (a) get back there again quickly (b) add watches for the expressions you found.

Wouldn't it be great if Unison had something like this?

Here's a sketch of what it might look like. I'm assuming a console-based UI, rather than anything more flashy.

Sketch of a Unison execution explorer

Let's fire up the explorer on some of the fuzzy string matcher code from Paul's recent blog post - we type this at the Unison prompt.

That drops us into the following view of the sliding function.

Notice how we're straight away actually looking at our code. And right underneath it we have some values, including the overall value of the outer expression we're exploring, and the function arguments, in this case t. You can see a couple of other bits and pieces on the screen too - I'll explain those shortly.

A bunch of the code is shown in blue, and this part, the 'focussed expression', also has its value displayed. Let's use the arrow keys to zoom the focus inwards to part of the syntax tree, and end up with the following:

Now, unfold is actually doing the heavy lifting here, so lets hit 'enter' to take a look inside it.

Those asterisks on the left of the code now start to make sense: they're showing the lines that are actually hit during execution. We're hitting the Some branch of the pattern match.

Just above the code, it says sliding[1] / unfold [invocation 1 of 5]. This is the 'execution path' - it's telling us where we are in the flow of execution of our program. We're in the first (and only) invocation of sliding - hence sliding[1]; we're in sliding's call to unfold, and we're in the first invocation out of five of unfold.

We've got a few more expressions being displayed for us too - both function arguments, and the variables brought into scope within the match expression in the case block. The function value f is being displayed as sliding>step - step isn't a meaningful name outside the scope of sliding, hence the qualification.

Notice how the type of unfold is being displayed:

unfold : Text -> (Text -> Optional (Text, Text)) -> [Text]

Actually, in the source, it's

unfold : s -> (s -> Optional (a, s)) -> [a]

but the type variables are known since we're in the context of the call that sliding makes, so the signature is displayed with the concrete values substituted in here. (Maybe changing the signature like this is confusing - maybe the type assignments a = Text and s = Text should be down below the code.)

Let's now focus on the expression unfold s' f, and while we're at it, let's hit b to 'bookmark' this view.

The first line has changed from

exploring ‘sliding’ [bookmark 1 of 1]

to

exploring ‘unfold’ [bookmark 2 of 2]

We can jump between our bookmarks, either by typing the bookmark number, or by using the arrow keys to select the exploring line and going left or right. The bookmarks will also help us resume this debugging session later.

So, so far we've seen the 'outer' (first) invocation of unfold - the one that returns the final result. What about the other invocations? Let's hit 'page down' to see the next one (or we could arrow to the execution path and then arrow right.)

Notice how we're now on

sliding[1] / unfold [invocation 2 of 5]

We still have the same expression focussed, but its value has changed, to [“ic”, “ci”, “ia”].

Now let's skip all the way to the fifth and last invocation.

Noticed how an asterisk has moved, showing that this time we're hitting the None branch. And there are no values for a and s' being displayed any more.

Let's say we want to understand why this is the last invocation, so we focus on the f s, the scrutinee of the case statement.

And then we hit enter to explore inside it.

Now let's focus on the Text.size t, and also make a bookmark while we're here.

Now we understand that we're down to only one character left from the end of the original input string - we can see that t is just "a" from the end of "Alicia", and that we're taking the length of that string and finding it to be less than 2, hence the None. Let's imagine that we're now happy we understand how this is working. Before we quit the explorer session, let's hit t to dump a transcript.

Here's the transcript that gets dumped to file.

This is a list of watch expressions, but with some exotic-looking qualifications separated by >:. Taking the second watch expression, we have sliding[1]/unfold[2], an 'execution path' saying that we're interested in the first invocation of sliding, and within that, the second invocation of unfold. And then we have case[2], a 'scope path', which points us to a scope within unfold, namely the second branch of the case statement, in which the expression unfold s' f makes sense.

What happens if we load these watch expressions again at the Unison prompt?

• The first is just showing us the expression we started the explorer session with, which is bookmarked automatically.
• The second is showing us the first bookmark we made ourselves, when we had focussed unfold s' f, within the second case branch of the second invocation of unfold.
• The third is showing us our second bookmark, when we'd focussed Text.size t within sliding>step from within the fifth invocation of unfold.

We can come back to those watch expressions and re-evaluate them in the normal way, even as we change the code. Some changes (like if we get rid of the call to unfold from sliding) are going to invalidate the watches, and we might need to replace them by exploring the code again (or maybe by manually editing the watch expression.)

We can also load that transcript up using the explorer, and it will bring us back to here.

Execution paths and scope paths

There are two mini-languages being proposed here: for execution paths like sliding[1]/unfold[2], and scope paths like case[2]. (Just to be clear, I'm not proposing that these are part of the Unison language proper - you can't write this stuff in your programs. So the >: (or whatever) is demarcating what's actually a Unison expression in a watch statement and what's not.)

Execution paths seem (to me) clearly useful things - the explorer will need to have them at least internally, so why not surface them so the user has a way of thinking and talking about a point in the execution as well. I'm sure that implementing them would be significant work in the interpreter, for it to be able to track its progress through one of these paths, but it seems like the sort of concern it's legitimate to make an interpreter deal with.

You could imagine doing more with them:

• sliding[1]/unfold[s = "licia"] to get all the invocations of unfold with a given argument value
• unfold[*] to get all the invocations of unfold, period
• using them to specify traces you want to see: > sliding "Alicia" >: sliding>step[*] >: "step, t =" ++ show t to show me all the values of t that sliding>step is invoked with.

Scope paths on the other hand, like case[2] to specify a sub-scope within a function, seem more dubious. The point is so we can name variables that are introduced within a sub-scope, to evaluate them. There's something similar going on with sliding>step. On the one hand, it doesn't seem ridiculous to me that terms in a language, which are values of a glorified tree type, should have an accompanying path type to traverse that tree. (Something about zippers?) On the other hand, it's quite a lot of complication to put in people's faces. But at least these paths would be being generated by a tool. Anyway, this area would need attention from someone with more language-technical nous than me, to develop it and judge if it was viable.

Various comments

• I'd prefer to call it something like the 'explorer', rather than the 'debugger'. Calling it the debugger suggests you'd only want to examine how code runs when it's not working, but really, seeing how it runs should be part of understanding it.

• I think this tool will probably require that the code it's running is pure, or at least, can be run with pure ability handlers. It's going to want to evaluate various expressions and sub-expressions over and over again. If it is pure-only, then it could still be useful for impure code, e.g. some program in IO, if we had record/replay in place - see Record/replay for Unison #258. Record/replay is basically a way of replacing all the handlers with pure ones, which replay information into your program from trace of a previous, 'real' run.

• I'm proposing this as a curses-style terminal app, like top. Probably this is not the zenith of UI environments, but at least (a) it could embed into the core Unison CLI app, so that the explorer was just part of the basic furniture, and (b) it would be a good foundation for a future GUI/IDE take on the same concept.

• The navigation inside the code of a function using the explorer, zooming into sub-expressions using arrow keys, is a well-ploughed furrow - Paul has implemented it already in previous incarnations of Unison! And Lamdu also shows how this can be done.

• We'd probably need something to explore a value as well ('data explorer'?) - values can get pretty big. Bonus points for jumping from a given constructor to the point in the execution that created it! (Or all points that match on it...)

• Thinking about code using the State ability, you'd want to be able to see that state in the explorer. I'm not quite sure how that would work. This is probably important! Maybe the UX for viewing the linear evolution of state over time should be different to drilling into evaluation of a single term.

• As and when Unison supports compiling to native code, I think it would be fine for the debugger to only work in interpreted mode. (ghci takes the same approach.) Ideally the fallback to interpretation would be transparent though.

Evaluation

In some ways, this is just like the standard imperative debugger experience you get in Visual Studio, albeit through the grainy lens of a console window! You see the code in front of you, and you can see the values of variables, evaluate expressions, and you go up and down the stack.

But it's worth highlighting some interesting extras in this proposed Unison experience.

• You can go backwards through evaluation as well as forwards.
• It's persistent - you can come back to the same view of the code execution later, without having to rerun the same procedure of breakpointing and stepping.
• It's adapted for an expression-oriented functional language: you can see the value of any expression, by focussing on it.

Precedent / related work

I'll confess I haven't taken much time to look around at what's already out there yet - here's a quick skim from googling. I was looking for stuff that played with the fundamentals, but mostly the more developed end of what's out there at the moment seems to just give you the VB6 experience: the code is in front of you, you have a watch window, you can see the stack frames, you can step forwards (only), you can run to a breakpoint. Probably there's interesting stuff in the academic literature from decades past - if you have links please reply with them!

Here's the not-so-standard stuff I did find:

For Haskell, Hat can do some neat stuff.

• for a given function, show all the arguments it receives and results it produces, throughout program execution
• wind a result value back to see what equations produced it
• explore the code, drilling down into function calls, showing arguments and results along the way - this bit hat-explore is the closest to what I'm proposing above, although it can't do the arrows-to-focus trick
• detect faulty subexpressions by asking you to label a series of computations as correct or faulty in a kind of bisection procedure.

I learn from the bottom of this page that Hat hasn't kept pace with the Haskell language, so is generally not useful now. This strengthens my suspicion that the debugger deserves a place in amongst the core Unison tooling.

Elm has record/replay, with a (currently basic) state timeline viewer for replay.

lamdu gives you runtime values overlayed much closer over the code - you can see the value taken by each subexpression.

More standard offerings

Racket has a GUI debugger, screenshot on this page.

Purescript currently has a barebones console debugger where you have to instrument your code with the places you want to add breakpoints.

Swift lets you set breakpoints from its REPL.

Imperative .NET languages have the Visual Studio debugger, which basically gives the classic VB6 experience, with lots of polish.

I'm not sure about the situation with Scala debuggers. scala-debugger.org seems to be about setting breakpoints by instrumenting the code. Maybe it's meant to be used via Eclipse. IntelliJ seems to be smoother - VB6 style.

gdb and lldb exist! I'm not sure about lldb, but gdb lets you step through execution, set breakpoints, and read variables. These tools are geared towards debugging compiled binaries. gdb lets you load and inspect the memory image of a crashed process.

[runarorama]

This is great! I really like the ideas here and would like to see this kind of thing happen in Unison for sure.

[atacratic]

Ideas for visualising expression evaluation: https://www.columnal.xyz/design-blog/debugging-display

[sullyj3]

Here's some more prior art from Bret Victor: https://youtu.be/8QiPFmIMxFc?t=984

[atacratic]

I'm getting excited about this idea again! I'm planning to start work on it.

In a nutshell, the plan is to implement the 'explorer': a terminal-based replay debugger, that (a) surfaces the actual code in the UI, and (b) allows you to save/load debugging sessions.

I've been thinking about how to break it down into phases, each delivering something useful:

1. Tracing of function calls and variable bindings, to file. This develops some of the underlying technology for the full explorer.
2. 'Code explorer', i.e. an interactive function browser that lets you select and follow references. This is independent of 1, and develops the terminal UI machinery for the full explorer.
3. The first incarnation of the full explorer: initially just a bare-bones debugger supporting run-to-breakpoint, and showing variable bindings. This builds on the first two phases.
4. Add on 'play/rewind' - i.e. use checkpoints of interpreter state to simulate reverse execution.

Plus you can imagine a bunch of further enhancements that would make sense on top of this central stuff (like the save/load session thing).

These phases are explained in more depth in the sections below.

I'm thinking my progress on this will be measured in years rather than months, but I reckon I'll get started anyway. If someone reading this wants to get involved and take on some pieces, that would be cool! Would be fun to collaborate on it. Get in touch with me on slack if you might be interested. I'm not suggesting/expecting the core team to get involved with implementation - I think they should stick to their other priorities. But for sure I will need their ideas and help/review with design work.

Questions

Here are the key questions where I need input/blessing from the core team. Arya and Runar are already on this thread; paging @pchiusano too.

• Please can we keep the Rt1 interpreter, even as and when we have a newer faster one (Design and implement faster runtime #1055 @dolio - very exciting!!) I'm proposing to add the debugging capabilities needed by the explorer just to the Rt1 runtime. I can read and understand Rt1 and I can even imagine enhancing it - I doubt I will be able to say the same for something super-optimized. There's clearly a tradeoff here - having multiple runtimes all under active maintenance will generate more work. But to me it makes sense to keep a 'reference and debug' runtime, even when we have a warp speed one as well.
• Obviously there's lots of design work to do, but assuming that all ends up satisfactory, will you be happy to take this stuff into master? Do you have any doubts about the overall direction here? Particular things to think about:
  • I'm proposing that the UI for this (at least the initial one that I write) use the terminal, rather than a web browser, or a plug-in for an editor or IDE.
  • This will be another way to explore Unison code, on top of the plans for the elm-browser, and any future browser-based structure editor.
  • As is made clearer below, I'm proposing this only works for pure computations, or for after-the-fact replays of IO computations. No attaching to live IO programs. (But the tracing bit, phase 1, can work fine for those.)
  • None of this will work directly with other runtimes or with code generated by a future LLVM backend. But you could certainly record runs that happen in those targets, and then replay them in the debug runtime for analysis, which seems pretty good to me.

Tracing

Let's have an option to get the Rt1 runtime to emit tracing of function calls and variable bindings, to a file.

The output might look like the following. This is a mock-up of how it would look from the example in the post above. In the trace, you can see a stack depth counter on the left. Each line is showing a couple of levels of the stack, plus information like argument values, return values, and which match was chosen within a case expression. (Maybe it could be improved with some tabulation/alignment.)

  1 sliding[1], t = "Alicia"
  2 sliding[1]/unfold[1], s = "Alicia", f = sliding>step
  3 ../unfold[1]/sliding>step[1], t = "Alicia"
  4 ../sliding>step[1]/Text.size[1], a1 = "Alicia", result: 6
  4 ../sliding>step[1]/Text.take[1], a1 = 2, a2 = "Alicia", result: "Al"
  4 ../sliding>step[1]/Text.drop[1], a1 = 1, a2 = "Alicia", result: "licia"
  3 ../unfold[1]/sliding>step[1], result: Some ("Al", "licia")
  2 sliding[1]/unfold[1], case 2: Some (a, s'), a = "Al", s' = "licia"
  3 sliding[1]/unfold[2], s = "licia", f = sliding>step
  4 ../unfold[2]/sliding>step[1], t = "licia"

  ... -- lines omitted from example for brevity

  7 sliding[1]/unfold[6], case 1: None
  7 sliding[1]/unfold[6], result: []
  6 ../unfold[5]/cons, a1 = "ia", a2 = [], result: ["ia"]
  6 sliding[1]/unfold[5], result: ["ia"]
  5 ../unfold[4]/cons, a1 = "ci", a2 = ["ia"], result: ["ci", "ia"]
  5 sliding[1]/unfold[4], result: ["ci", "ia"]

  ... -- lines omitted

  2 sliding[1]/unfold[1], result: ["Al", "li", "ic", "ci", "ia"]
  1 sliding[1], result: ["Al", "li", "ic", "ci", "ia"]

This proves out a bunch of machinery that's needed in the interpreter for the full explorer, doesn't require a lot of extra work on top, and delivers something pretty useful. No more debugging with trace statements! 😎

Key bits of work needed:

• Annotation of the IR with data correlating back to the Term from which it was compiled. (~'debugging symbols') Design for this part is step 1 of this whole project.
• A type and a parser/printer for execution paths, like sliding[1]/unfold[1].
• Extend the interpreter to write the trace.

Interesting issues:

• Design for the IR annotation and how to build it up through each compilation phase. Back-compatibility / codebase upgrade.
• How we deal with: handlers and ability requests; anonymous lambdas; tail recursion.
• How will this interact with pluggable syntax?
• Is there a useful interim step, where we don't have execution paths yet, and just output on each trace line the name of the function at the top of the stack? Probably yes.

Code explorer

Let's have an interactive terminal-based code browser embedded in ucm - like less but with the ability to follow a reference to jump into a subfunction.

It might look like the following. Arrow keys navigate which function call is highlighted (blue) - enter jumps to showing that function. (The 'e' option to edit is equivalent to running the ucm edit command - it prepends the function to a scratch file.)

This is independent of tracing support.

This builds up the terminal infrastructure needed for the full explorer. It might also be handy to have a terminal-based browser for a local codebase, even if that ends up duplicating a browser-based one someday. The code explorer is a bit like the 'offline mode' for the full explorer: you can browse the code, but it's not actually running.

Key bits of work needed:

• Select and integrate an ncurses-style terminal library.
• Navigation and focussing.

Interesting issues:

• Finding a terminal library might be frustrating. I didn't immediately see one that (a) is non-GPL, (b) has a nice API, (c) supports Windows.
• Focussing does not yet necessarily need to support focussing arbitrary subtrees - maybe just references.

Run to breakpoint

Let's run the interpreter til it hits the user's chosen breakpoint (execution path), freeze it, then allow the user to inspect the functions that are in the stack using the code explorer, and see values of arguments and variables.

This takes the IR annotations and interpreter instrumentation from the tracing phase, and brings it together with the code explorer into something just about recognisable as a barebones debugger.

Key bits of work needed:

• Expose interpreter/program state via a 'control and inspect' API.

Interesting issues:

• Making the API usable by other clients. (What clients might those be?)

Play/rewind

Let's allow the user to wind program execution forwards and backwards, either step-by-step or to the next breakpoint.

Rewind will use a cache of snapshots of interpreter/program state - actual evaluation only ever runs forwards. We can simulate going backwards to time N by going forwards from a snapshot from time M, where M<N.

Key bits of work needed:

• Add snapshot/replay logic and heuristics under the control API.

Interesting issues:

• Space/time trade-offs around snapshot/replay. Responsiveness when stepping backwards. This paper (Tolmach and Appel '93, §7.5) about the standard ML debugger describes a simple cache of recently used snapshots ('checkpoints').
• Do we use persistent data structures in the interpreter and does that give nice sharing behaviour between snapshots?
• Note the snapshot/replay approach requires the computation to be pure*. So for IO programs this requires Record/replay for Unison #258, an IO handler that tees program input off to a log for later replay. (Note that that in turn requires typed durable storage support to store the logs.) * pure apart from reading the log
• The other strategies for getting this kind of 'time travel debugger' are (a) output all the information you could ever need, the first time you run the program, and (b) supporting actual reverse execution (using some kind of log to retrieve information destroyed during forwards execution.) (a) seems hard compared with just logging IO inputs, which is doable in Unison library code, thanks to purity. (b) also seems hard, although maybe not a memory-hungry as snapshot/replay.

Further enhancements

• Focus arbitrary sub-expressions.
  • Display their value.
  • Display their type. Imagine how useful that would be for understanding code! Note this could be done just on top of the code explorer: breakpoint/play/rewind not required.
• Save/load transcripts of debugging sessions. Bookmarks.
• Watch expressions; i.e. enter Unison expressions to be evaluated and displayed alongside variable values.
• Data explorer; i.e. hit 'enter' on a value to give it the whole screen. Lots of values are going to be too big to fit on one line.
• Something about visualizing the evolution of state?
• Use the explorer to build filters to apply to program traces - e.g. 'dump out the trace just from these two functions'.
• Provenance back-tracking: i.e. given a focussed expression which seems wrong, make a single keystroke to focus all its constituent inputs and their values. (Then rinse and repeat.) Seems like it should be easier than this (Booth and Jones, '97) makes it sound.
• Given a constructor within a value, jump to the point in the execution that created it. Or walk through all the points that match on it.

[atacratic]

I missed a couple of points on the question of doing this in Rt1 vs Rt2.

In favour of maintaining two runtimes, one for debug one for speed:

• Adding debug instrumentation code might make the runtime slower, even when debugging is not switched on. And it adds complexity and distracts from the core mission of being fast.

But on the other hand:

• Is it obvious that the two runtimes would always produce identical results? When writing the above I was taking that as a given (modulo bugs). But reading @dolio's explanatory comments on Rt2 I'm wondering whether there is room for semantic differences in behaviour, for example around nested handlers. Getting different behaviour only when debugging would be pretty confusing.

Observation:

• With two runtimes it looks like we'd have two sorts of IR to store in the codebase (unless Rt1 was either dumped or rewritten to use the new IR). That's related to the question of maybe storing IR both with and without debugging symbols.

[matssk]

It would be cool with a debugger with a bunch of built in visualizations for the data plus the ability to create new visualizations, for example for new data structures.

Then you could get the debugger to create visualizations like these while implementing for example a new algorithm

https://visualgo.net/en