this is a very nice result and promises to be very useful, if i am understanding it correctly. i was skeptical that they could find anything new to say in 02024 about such a well-studied problem, but the paper surprised me; they do. in fact there are many delightful things in this paper, starting with their clean and general abstract interface for union-find! (even though union-find is just their motivating example rather than anything central to the paper)
in essence, i think their proposal is to journal all the updates to your mutable store, in much the same way that transactional memory does, so that you can travel to any past or future state by replaying the journal of updates; if you change the past, you cause the timeline to diverge, but you don't lose the ability to travel back to the original timeline, because you can journal-replay your way back to the divergence point. unlike transactional memory, they don't do anything special on reads of mutable state, just writes. because they're testing on algorithms that mutate state sparingly, they get very good efficiency. moreover, their comparison is with the same algorithm using plain ocaml references, but ocaml's write barrier makes it expensive to mutate state anyway, so their efficiency looks even better
they avoid storing redundant journal entries between snapshots by using a generation counter that counts snapshots, so repeatedly mutating the same reference doesn't keep allocating memory; it just repeatedly checks the generation counter
i wonder to what extent you can combine their algorithm with umut acar's 'self-adjusting computation' to get a generic, efficient way of converting an imperative program into an incremental dataflow program?
perhaps inspired by union-find, their tree of store states is made out of only parent pointers, so you can walk up the tree (from a snapshot) to the root, but never back down. (a new child node is constructed for each parent when you do this.) this allows garbage collection to work on saved snapshots! however, a live snapshot can still keep alive an otherwise unreferenced mutable reference, even though there's no way for the user of the snapshottable store to access it
they credit fully fp-persistent shallow binding to henry baker. i don't think that's fair, much as i appreciate his work; baker himself credits shallow binding to maclisp, citing moon's maclisp reference manual, and the more capable version he describes to greenblatt's lispm, each from four years earlier. and i don't think moon or greenblatt would claim full credit for it either, nor would they claim it only dated from 01974; what was new in greenblatt's design was that it could handle lexical scoping and upward funargs, while older implementations of shallow binding could only handle dynamic scoping and downward funargs. this is the difference between 'persistence' and 'semi-persistence' in the terminology of allain et al., as they explain on page 4. to a great extent what baker was doing was explaining the technique rather than claiming credit for it
this reminds me of a section from the mother of all multics emacs papers (https://www.multicians.org/mepap.html), by bernie greenberg, about the first lisp emacs, which was written in maclisp
> The implementation of multiple buffers was viewed as a task of
multiplexing the extant function of the editor over several buffers.
The buffer being edited is defined by about two dozen Lisp variables
of the basic editor, identifying the current Editorline, its current
(open/closed) state, the first and last Editorlines of the buffer,
the list of marks, and so forth. Switching buffers (i.e., switching
the attention of the editor, as the user sees it) need consist only of
switching the values of all of these variables. Neither the interactive
driver nor the redisplay need be cognizant of the existence of multiple
buffers; the redisplay will simply find that a different “current
Editorline” exists if buffers are switched between calls to it.
What is more, the only functions in the basic editor that have to be
aware of the existence of multiple buffers are those that deal with
many buffers, switch them, etc. All other code simply references the
buffer state variables, and operates upon the current buffer.
> The function in the basic editor which implements the command that
switches buffers does so by saving up the values of all of the relevant
Lisp variables, that define the buffer, and placing a saved image
(a list of their values) as a property of the Lisp symbol whose name
is the current buffer’s. The similarly saved list of the target
buffer’s is retrieved, and the contained values of the buffer state
variables instated. A new buffer is created simply by replacing the
“instatement” step with initialization of the state variables to
default values for an empty buffer. Buffer destruction is accomplished
simply by removing the saved state embedded as a property: all pointers
to the buffer will vanish thereby, and the MacLisp garbage collector
will take care of the rest.
> The alternate approach to multiple buffers would have been to have the
buffer state variables referenced indirectly through some pointer which
is simply replaced to change buffers. This approach, in spite of not
being feasible in Lisp, is less desirable than the current approach,
for it distributes cost at variable reference time, not buffer-switching
time, and the former is much more common.
> One of the most interesting per-buffer state variables is itself a list
of arbitrary variables placed there by extension code. Extension code
can register variables by a call to an appropriate primitive in the
basic editor. The values of all such variables registered in a given
buffer will be saved and restored when that buffer is exited and
re-entered. The ability of Lisp to treat a variable as a run-time
object facilitates this. Variables can thus be given “per-buffer”
dynamic scope on demand, allowing extensions to operate in many
buffers simultaneously using the same code and the same variables,
in an analogous fashion to the way Multics programs can be executing
in many processes simultaneously.
to some extent this reflects the computer architectures that were current at the time (nowadays indexing off a base pointer in a register is usually faster than accessing memory at an absolute address) but the overall principle is still applicable; it just manifests in different ways
but of course what allain et al. have implemented is much more efficient at switching contexts, because it only updates the references that are different between the two contexts
this paper is timely for me because, entirely by coincidence, i implemented dynamic scoping with shallow binding in ansi forth last week:
short example usage, a word to print a number in decimal regardless of what the current base is:
decimal : dec. 10 base let! . ;
because this stores the saved value on the return stack, it is 'semi-persistent' in the terms of this paper; once you have undone an update, you cannot redo it
longer example:
variable src variable dest variable stor variable n
defer move-disc
: text-disc
cr ." Move disc " n @ . ." from " src @ emit ." to " dest @ emit ;
' text-disc is move-disc
: hanoi ( src stor dest n -- )
n let! dest let! stor let! src let!
n @ 0= if exit then
src @ dest @ stor @ n @ 1- recurse
move-disc
stor @ src @ dest @ n @ 1- recurse ;
char A char B char C 4 hanoi
this code should surprise you if you are familiar with the conventional wisdom that standard forth doesn't have local variables!
(it's a pretty inefficient implementation though)
and, also entirely by coincidence, i implemented union-find in forth a couple of weeks earlier than that: https://asciinema.org/a/672405
in essence, i think their proposal is to journal all the updates to your mutable store, in much the same way that transactional memory does, so that you can travel to any past or future state by replaying the journal of updates; if you change the past, you cause the timeline to diverge, but you don't lose the ability to travel back to the original timeline, because you can journal-replay your way back to the divergence point. unlike transactional memory, they don't do anything special on reads of mutable state, just writes. because they're testing on algorithms that mutate state sparingly, they get very good efficiency. moreover, their comparison is with the same algorithm using plain ocaml references, but ocaml's write barrier makes it expensive to mutate state anyway, so their efficiency looks even better
they avoid storing redundant journal entries between snapshots by using a generation counter that counts snapshots, so repeatedly mutating the same reference doesn't keep allocating memory; it just repeatedly checks the generation counter
i wonder to what extent you can combine their algorithm with umut acar's 'self-adjusting computation' to get a generic, efficient way of converting an imperative program into an incremental dataflow program?
perhaps inspired by union-find, their tree of store states is made out of only parent pointers, so you can walk up the tree (from a snapshot) to the root, but never back down. (a new child node is constructed for each parent when you do this.) this allows garbage collection to work on saved snapshots! however, a live snapshot can still keep alive an otherwise unreferenced mutable reference, even though there's no way for the user of the snapshottable store to access it
they credit fully fp-persistent shallow binding to henry baker. i don't think that's fair, much as i appreciate his work; baker himself credits shallow binding to maclisp, citing moon's maclisp reference manual, and the more capable version he describes to greenblatt's lispm, each from four years earlier. and i don't think moon or greenblatt would claim full credit for it either, nor would they claim it only dated from 01974; what was new in greenblatt's design was that it could handle lexical scoping and upward funargs, while older implementations of shallow binding could only handle dynamic scoping and downward funargs. this is the difference between 'persistence' and 'semi-persistence' in the terminology of allain et al., as they explain on page 4. to a great extent what baker was doing was explaining the technique rather than claiming credit for it
this reminds me of a section from the mother of all multics emacs papers (https://www.multicians.org/mepap.html), by bernie greenberg, about the first lisp emacs, which was written in maclisp
> The implementation of multiple buffers was viewed as a task of multiplexing the extant function of the editor over several buffers. The buffer being edited is defined by about two dozen Lisp variables of the basic editor, identifying the current Editorline, its current (open/closed) state, the first and last Editorlines of the buffer, the list of marks, and so forth. Switching buffers (i.e., switching the attention of the editor, as the user sees it) need consist only of switching the values of all of these variables. Neither the interactive driver nor the redisplay need be cognizant of the existence of multiple buffers; the redisplay will simply find that a different “current Editorline” exists if buffers are switched between calls to it. What is more, the only functions in the basic editor that have to be aware of the existence of multiple buffers are those that deal with many buffers, switch them, etc. All other code simply references the buffer state variables, and operates upon the current buffer.
> The function in the basic editor which implements the command that switches buffers does so by saving up the values of all of the relevant Lisp variables, that define the buffer, and placing a saved image (a list of their values) as a property of the Lisp symbol whose name is the current buffer’s. The similarly saved list of the target buffer’s is retrieved, and the contained values of the buffer state variables instated. A new buffer is created simply by replacing the “instatement” step with initialization of the state variables to default values for an empty buffer. Buffer destruction is accomplished simply by removing the saved state embedded as a property: all pointers to the buffer will vanish thereby, and the MacLisp garbage collector will take care of the rest.
> The alternate approach to multiple buffers would have been to have the buffer state variables referenced indirectly through some pointer which is simply replaced to change buffers. This approach, in spite of not being feasible in Lisp, is less desirable than the current approach, for it distributes cost at variable reference time, not buffer-switching time, and the former is much more common.
> One of the most interesting per-buffer state variables is itself a list of arbitrary variables placed there by extension code. Extension code can register variables by a call to an appropriate primitive in the basic editor. The values of all such variables registered in a given buffer will be saved and restored when that buffer is exited and re-entered. The ability of Lisp to treat a variable as a run-time object facilitates this. Variables can thus be given “per-buffer” dynamic scope on demand, allowing extensions to operate in many buffers simultaneously using the same code and the same variables, in an analogous fashion to the way Multics programs can be executing in many processes simultaneously.
to some extent this reflects the computer architectures that were current at the time (nowadays indexing off a base pointer in a register is usually faster than accessing memory at an absolute address) but the overall principle is still applicable; it just manifests in different ways
but of course what allain et al. have implemented is much more efficient at switching contexts, because it only updates the references that are different between the two contexts
this paper is timely for me because, entirely by coincidence, i implemented dynamic scoping with shallow binding in ansi forth last week:
short example usage, a word to print a number in decimal regardless of what the current base is: because this stores the saved value on the return stack, it is 'semi-persistent' in the terms of this paper; once you have undone an update, you cannot redo itlonger example:
this code should surprise you if you are familiar with the conventional wisdom that standard forth doesn't have local variables!(it's a pretty inefficient implementation though)
and, also entirely by coincidence, i implemented union-find in forth a couple of weeks earlier than that: https://asciinema.org/a/672405