ballingt

Interactive Interpreter Undo

13 Sep 2016

>>> print(42 + 7)
51
>>> colors = ["purple", "orange"]
>>> print(colors)
["purple", "orange"]
>>> colors.append("red")
>>> print(colors)
["purple", "orange", "red"]

I have found undo immensely useful in interactive interpreters for the same reasons we found it useful in Colossal Cave Adventure. Making exploration more risk-free and status check commands easier to sweep away makes me more comfortable exploring. Undo also makes more precise management of screen real estate possible, making it easier for an audience to follow along with a live coding session. The document which we modify and to which we undo changes to is the interpreter: what names, like “color”, are defined, and to which objects they refer. However, most interactive interpreters are capable of a wider variety of actions, some of which affect the world beyond the interpreter state. This will make implementing undo more difficult than it would have been for Colossal Cave Adventure.

The wide variety of commands issuable to an interactive interpreter makes recording each action and the effects of these actions in order to reverse them later, the first of the three undo strategies, more difficult: it would be a lot of work to write reverse versions of every command. Finding the differences between two interpreter states might be possible for interpreters written from scratch with these inspection capabilities in mind, but typically this is not easily accomplished. Modifying an existing interpreter to record these changes might be possible, similar to the way some of Philip Guo’s modified Python interpreters are instrumented to record additional information about the state of the interpreter.

The third undo approach is a natural fit for interactive interpreters that have serialization of session state built in. Matlab and R are languages that, like Colossal Cave Adventure, have built-in commands to save their current state to a file which can be used to restore that state later. Implementing undo for an interpreter of one of these languages might involve saving snapshots after each run command and restoring the previous one on undo, along with a bit of extra work to save and restore command outputs.

Some actions taken in an interactive interpreter cause changes of too large a scope for any of these undo techniques. In this video a programmer is confused when undo fails for cases involving the filesystem or online shopping.

If the scope of undo does not extend beyond the state of the interpreter, we’ll have to give up on truly undoing commands like deleting a file or communicating with other computers. A virtual machine or some other system-level monitor might make changes to the filesystem undoable, but figuring out a generic way to undo network communication is difficult. Gmail implements a single undo step for sent emails by recording the user’s intent to send the email but not acting on it for 30 seconds. Recording intent to interact with the outside world instead of actually doing so makes sense for actions that are asynchronous from the users’s perspective, like sending an email, but generally in order to provide the result of a command as feedback that command needs to take place immediately. Another approach might be to record intent and predict the result of a command. Our undo will simply remove such a command and its associated output from the screen.

Undo in bpython

The first place I encountered this style of undo in a command line interface was with bpython. To try out undo, run pip install bpython, run bpython, run a command, and then hit ctrl-r. (reverse-i-search is bound to meta-r by default, but you can swap these back with a config file)

bpython is an interactive interpreter interface for Python that has had undo for a long time, and this undo has always erased the undone command and its output. Initially bpython used an alternate screen display that did not integrate with other commands in a shell session. I wrote a new frontend to make bpython history integrate with the parent shell process history, which required some interesting terminal techniques. Through making these changes and subsequent work on bpython, I became familiar with and made some changes to its undo functionality.

bpython implements undo using the second of the three previously outlined strategies: rerunning every command except the most recent in order to recreate the previous state. When the user requests an undo, a new object representing an interpreter is created with a clean slate of global variables. Then the previous state is progressively rebuilt by rerunning all previous commands except the most recent.

There are some serious issues with this approach. Sometimes side effecting actions being run again causes unwanted effects. Sometimes rerunning a long history of commands takes considerable time. Sometimes running a command doesn’t produce the same output when it is run a second time: read files might now contain different bytes, a server might return a different response, or a pseudorandom number generator might produce a different result. Because bpython runs the new interpreter in the same process, some state shared between all interpreter objects in a process fails to be reset before rerunning the command history. This shared state includes the cache of imported modules (stored in sys.modules) and per-process values like the current working directory and environmental variables.

To mitigate the delay caused by re-executing commands, I added a cumulative calculation clock to bpython to be used as an estimate for re-execution time. Once this clock reaches 1 second, the user is given the opportunity to undo more than a single command at once, to avoid rebuilding states several times for consecutive undos. Some commands, like calling up interactive help and waiting for user input, are patched to be less disruptive (not bring up a pager) and more reproducible (returning the same value they got the first time) during undo-triggered re-execution. Dealing with commands that interact with the outside world, also known as IO for Input/Output, is one of the most interesting topics in implementing undo, but bpython doesn’t do anything special in the majority of cases.

bpython takes advantage of this otherwise limiting approach to rebuilding state to implement related features. The module cache not being cleared during undo allows module reload to be triggered separately by the user with F6, allowing quickly checking the effect of modifications made to a module. Because each undo reruns the entire session, it’s possible for the user to edit that session before it is rerun with F7.

Before I added it, bpython didn’t implement the first half of the “rebuild from a known initial state” strategy: it didn’t use a new interpreter object with new global variables. Interestingly this often worked: rerunning all but the most recent Python command from the current state often approximates the previous state well enough be useful.

Because rebinding of variables is allowed in Python, including redefinition of functions and classes, running previous commands on top of current state indeed creates a state similar to the previous one. But with this technique variables would end up defined that shouldn’t have been, which in combination with Python’s inspection abilities to do things like ask whether a variable name is defined resulted in inconsistencies in recreated states that could affect code.

    >>> a = 1
    >>> 'b' in locals()
    False
    >>> b = 2
    >>> <undo>
    >>> 'b' in locals()
    True

The older strategy is still used in cases where the initial state cannot easily be reproduced, as when it is executed from a debugger with existing initial state. In this case bpython could either disable undo or provide it in this more limited way.

This is an important decision. Providing a tool that doesn’t behave as expected can be worse than not providing it at all.

bpython has a lot of bugs generally; I’m too set in my ways to to notice many of them, but I’d guess the Dan Luu time-to-first-bug would be in the double digit seconds. I find the payoff high enough and the cost of checking behavior in regular Python low enough that using it is worth it to me.

Similarly, I appreciate undo so much that I prefer this weaker undo to not providing the feature at all when the initial state can’t be recreated. However, we’ll see that we can use better undo techniques to avoid some of these problems.

Rerunning history in a new process

Although creating a new InteractiveInterpreter object improves the reproducibility of the initial state from which undo states are constructed, global state like the module cache, the current recursion limit, and other general process state like the current directory and environmental variables all persist across the creation of a new interpreter object. The cleaner solution would be to start a new Python process for each reproduced state for undo. Logging commands and running them in a new process is a relatively general way to reproduce a process state, and could be used for many command line interfaces. Here’s a rough general wrapper for this with very primitive terminal rewriting, and a Haskell interactive interpreter wrapper that works similarly.

Notebook view of a long-lived REPL

You can try out a similar undo manually in a Jupyter notebook. Jupyter notebooks act as frontends to interactive interpreters in many languages that run as separate processes called kernels. These kernels can be restarted and commands, stored in the Notebook interface, can be rerun. The user could delete the most recent command, restart the kernel and re-execute to implement a manual undo. Current versions of the notebook even have a shortcut to restart the kernel and rerun all commands, making this a quick process.

However it’s common to make changes to previous commands in Jupyter notebooks without restarting the kernel, or to delete commands and their corresponding output if they’re purely informative or not useful. The notebook interface is strictly more powerful than undo: undo can be simulated as described above, but the fine-grained control of command output and ability to edit and rerun individual commands provide many of the same benefits as undo. The more limited undo paradigm might be preferred because modifying and rerunning commands from history out of order can obscure the history of execution, even removing evidence of the commands that were used to create the current environment.

Jupyter notebooks trade the display of a log of exactly the commands run so far for the ability to selectively edit and run commands from history. This makes it easier to redo a calculation later in a data pipeline without rerunning earlier steps in the pipeline. In contrast, systems with only undo always preserve a single path by which the current environment can be reproduced.

I think Jupyter notebooks are amazing. I’ve used them with Haskell, R, Ruby, and JavaScript in addition to Python. If you’re not so far convinced by my exhortations to use undo, consider ignoring the rest of this post and proceeding directly to using and contributing to the Jupyter kernel for your favorite language. I would only consider arguing that undo is preferable in terminal interfaces to the Jupyter kernels, or for situations in which it’s difficult to keep a notebook reproducible.

Restoring state with fork(2)

Using a separate process for each undo allows a cleaner initial state, but rebuilding state from there can still cause unwanted side effects, and we’re still left with nondeterminism in interactions with the world beyond our process: changes to the contents of files, servers that might return different responses, etc. If only we had snapshots of the process, it wouldn’t be necessary to risk causing effects outside of the process again or risk requests getting different responses each time undo is used. It would be awfully nice to make copies of entire processes, and restore those copies as needed.

Fortunately making a snapshot of a process is possible on unix systems with the fork system call!

Each time this Python interpreter asks for input, it makes a copy of itself with fork. One of these copies goes to sleep for a bit while the other executes the entered command. If the user types “undo,” then that process dies and the other wakes up and resumes execution at that earlier point.

import code, os, sys
def read_line(prompt=""):
    while True:
        s = input(prompt)
        if s == 'undo':
            sys.exit()  # restores prev. state in parent
        if os.fork() == 0:  # this is the child
            return s
        else:  # this is the parent
            os.wait()  # wait for child process to die
console = code.InteractiveConsole()
while True:
    src = read_line('>>> ')
    console.runsource(src)

Fork works well enough for simple programs, but fork is dangerous. Once the process being forked has multiple threads all bets are off. And a good new bet is that things won’t work.

One of the difficulties of saving snapshots of an interpreter is the storage space required to keep track of them. Since these copies of processes are stored in RAM instead of being serialized to disk, there’s even less space available to store them. The copies of the process are quite similar to each other, and fork takes advantage of this similarity: portions of a process are only copied when one copy or the other makes a change to a portion of memory, called a page. This “copy-on-write” strategy means waiting to copy over of a block of memory to another block until one of the processes writes to that block. This means the amount of additional space required per copy depends on how many pages of memory are modified to execute a single command. Unfortunately, simple commands may result in changes to a large number of pages in interpreters not optimized for the fork system call. See this article on how this behavior was improved in version 2.0 of Matz’s Ruby Interpreter. It suggests this technique will work much better with interpreters that go out of their way to make forking efficient.

On my machine each fork of Python 2.7 takes between 200 to 1000 KB for “typical” interactive use, that is, not creating or loading large data structures. A better system might be more careful about when to fork, perhaps only maintaining enough copies of the process to support a few undos.

Hacking fork-on-command into interpreters

What if we wanted to use forking but not mess with interpreter internals? Command line interfaces often follow a pattern of calling a function from the GNU Readline library to get their next line of input. It’s possible to intercept these calls to readline and substitute a patched version that uses fork to copy the process, in a manner similar to the Python code above. This hijacking is accomplished by encouraging the executable to load a different shared library. On Linux this is done with LD_PRELOAD, on OS X with DYLD_LIBRARY_PATH. This hack requires that the interpreter executable loads the readline library dynamically, or else recompilation of the executable is required.

Since readline knows when undo is happening, it knows when the terminal display should be saved or restored by erasing some rows of output. The interpreter is run in a pty to cajole it into allowing its terminal output to be recorded and our patched readline library can send a message to the process controlling the pty in which the interpreter is running announcing when to record or restore terminal states. Now we have the undo we set out to obtain for many interactive interpreters without modifying them each individually.

This project is called rlundo after the useful wrapper program rlwrap. It’s a fun hack (and if you want to play with it, it could use some love). But it’s probably never going to be a robust solution. rlundo is a way to try out undo in your favorite interpreter so if you like it you can look at adding it in a less hacky way :)

Follow @ballingt

Thanks to Ezekiel Smithburg, Leah Hanson, Julia Evans, and Kamal Murhubi for feedback on this post. Thanks to Erin Murray, Vaibhav Sagar, Sarah Ransohoff, and Katherine Erickson for edits. Thanks to Mary Rose Cook for feedback on an early version of this post.