## The meaning of a program change is a change to the program's meaning

ROLY PERERA, The Alan Turing Institute, London, UK

## Programming as dialogue

Incremental computations [18, 26, 1, 14, 3] map input changes to output changes, ideally faster than running from scratch on the new input. The program itself is assumed to be fixed. It may be possible to replace functional inputs with other functions, but changes to the program text itself are not usually considered.

Programming is also an incremental endeavour [12, 11]. The focus here is on program changes, often in the context of a fixed input such as a test case. Since the entire goal is to bring about specific changes in behaviour, the output changes that arise are of great interest to the programmer. Live programming [25, 10, 13] and test-driven development [2] recognise this, but neither provides a fine-grained notion of change. New outputs appear wholesale, leaving it up to the programmer to figure out what changed and why.

This suggests a research problem: developing an incremental, fine-grained semantics which maps program changes to output changes, interpreting the meaning of program changes as changes to the program's meaning .

As a toy example, suppose I wish to compute the sum of the squares of a list of integers. I start with a simpler program, say a function which simply copies a list:

$$f _ { \ } [ ] = [ ] \\ f _ { \ } ( x \, \colon \, x s ) = x \, \colon \, f _ { \ } x s$$

As a sanity-check, I run my function at an argument:

1

f [1, 3] =&gt; [1, 3]

Perhaps seeking a 'tabular' view of the problem, I decide to pair each element with its square, making the following edit (new code is shown in green):

$$<_OCaml_> +      1  f  [] = []
+     2  f  ( x \, : x s ) = ( x, s q \, x ) \, : f  x s$$

I can now re-run the earlier test case, to check that the output has become [(1, 1), (3, 9)] . But what if the programming environment could directly interpret my program change as an output change?

$$\ 1 \ f \ [ 1, \ 3 ] \, \gg \, \left [ ( 1, \ 1 ), \ ( 3, \ 9 ) \right ]$$

These are, after all, the intuitive consequences of editing the program in the specific way that I did: my edit paired each element with its square (on the right). Here, for example, the output delta confirms my intuition that, of the two occurrences of 1 in the revised output, it is the second one which should be considered 'new'.

## Towards a semantics of program change

Rather than considering in detail how this might this work, we content ourselves with an informal exploration of the problem. Work on program slicing [21, 24] and live programming with holes [17] assigns meaning to incomplete programs and their (partial) completions;

this has some of the flavour of what we want, but is a rather monotone notion. To support structural reorganisations like moves and splices, we will suppose a term graph representation of programs [23], perhaps provided by a structure editor [4] able to assign unique addresses to subterms [20]:

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00898v1-figure-ecabe763-982e-4771-8e7a-e9ff6452a9fd.jpg)

The graphs on the left graphically represent the two defining clauses of f ; we place them side-by-side to establish them as disjoint parts of the same definition. Inputs nodes (patterns) are shown in white, and output nodes (values) in grey. The recursive call to f appears as an application node with no output edge.

The program edit is shown graphically to the right, as a 'graph delta' to the cons clause of the definition. The new pair constructor and its child edges, which should be read as pointers, are shown in green. The pointer to the first element of the output is dotted blue, meaning the pointer value has changed; this is necessarily the case here because it refers to a newly-created node.

What we seek, then, is a semantics that allows us to 'execute' the edit to the program to obtain a corresponding edit to its execution. Below left is the original execution of the test case, represented as a term graph with a shape resembling a big-step derivation:

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00898v1-figure-dbbc35cb-2e3c-4f3e-ba65-0e7e685d0252.jpg)

To the right is the modified execution we would like to obtain, with delta-colouring showing new nodes spliced into the computation in a way that accounts for the output delta identified previously. What this illustrates is that a suitable notion of execution delta should (we contend) 'operationalise', or account for, output deltas, generalising the idea from dynamic program slicing that parts of executions account for specific parts of the output [21].

In the other direction, we must seek an appropriate technical sense in which those execution deltas 'correspond' to the program deltas that gave rise to them. As an example of a potential property of interest, one might consider whether there exists a map from execution nodes to program nodes preserving the graph structure and delta colouring.

## Executing changes via changes in executions

Here is a rough sketch of the idea more formally. Suppose we already have a baseline big-step evaluation relation ⇒ 0 for our language. We start by defining a relation e ⇒ v for programs represented as term graphs, consistent with the baseline semantics in that e ⇒ v implies ∣ e ∣ ⇒ 0 ∣ v ∣ where ∣ e ∣ is the 'tree-unravelling' [5] of e . Then the idea would be to derive an incremental evaluation relation ⇒ δ satisfying:

$$e \Rightarrow v \text{ and } e, \delta e \Rightarrow _ { \delta } \delta v \text{ implies } e \oplus \delta e \Rightarrow v \oplus \delta v \text{ } ( 1 ) \quad \bar { \text{ad} }$$

where ⊕ applies a delta to a term graph. Note that this is quite different from the static differentiation problem [3, 6], since δe describes an arbitrary change to e .

Now, in our setting, it is always possible to compute the difference v ⊖ v ′ between two outputs v and v ′ , or more generally the difference D ⊖ D ′ between two executions D ∶ e ⇒ v and D ′ ∶ e ′ ⇒ v ′ , simply by comparing the term-graph representations [20]. So in fact we can always trivially exhibit a relation satisfying property (1) by defining e , δe ⇒ δ v ′ ⊖ v where e ⇒ v and e ⊕ δe ⇒ v ′ , supposing that ⊖ satisfies v ⊕ ( v ′ ⊖ v ) = v ′ [3].

We are left with at least two significant challenges, however. First, we must take care to balance precision with the integrity constraints of the term graph. We must define e ⇒ v so that distinct nodes are always used to represent distinct terms (so v remains a wellformed term graph), but also so that nodes are reused systematically in order to obtain precise deltas.

As an example of how nodes can be safely reused, suppose we extracted the expression (x, sq x) in the definition of f into a new function g , replacing free occurrences of x by uses of the argument y of the new function [7]:

$$<_OCaml_> f [] = []
f (x : xs) = g x : f xs

 g y = (y, sq y)$$

Such refactorings are common programming 'microsteps' [19]. They clearly have no effect on the output v considered as its tree-unravelling ∣ v ∣ . But we might also observe that although the expression responsible for constructing the pairs is now inside g , the values used to close that expression are the same as before. Moreover g simply delegates to that expression. So it should be safe to use the same nodes for the pairs in the new execution as we did in the previous one, and view the change simply as a 'rewiring' of the computation:

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00898v1-figure-1d775b2a-915c-4334-aff2-e7a8dfdbaa16.jpg)

On the other hand, given that f has now simplified to map g , suppose we adjusted our test case as follows:

$$n = \frac { 1 } { \text{ map } g \, [ 1, \, 3 ] } \, => \, [ ( 1, \, 1 ), \, ( 3, \, 9 ) ]$$

This is also a refactoring, and so again the output unravels to the same tree as before. But now a different expression (one found in the body of map ) is responsible for constructing the list nodes in the output. It would therefore be unsafe to use the same nodes as we did previously to construct the list, at least not without additional global knowledge (for example that f is not called anywhere). This explains the new lists nodes that were highlighted in the output delta above:

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00898v1-figure-4f4f7407-9788-4924-a9fa-b6fb257a9f36.jpg)

A second challenge is to efficiently implement ⇒ δ so that memoised [15] parts of a previous evaluation D ∶ e ⇒ v can be reused to produce D ′ ∶ e ⊕ δe ⇒ v ′ . This leads naturally to the question of whether existing approaches to incremental computation, in particular self-adjusting computation and related work [1, 8, 9], can be be brought to bear on this problem, by using a general-purpose incremental language as a metalanguage to derive an interpreter able to respond to program changes. While Hammer et al. [9] show that such an approach is possible, this technique does not in itself give rise to a direct program-change semantics for the object language, but rather one which is implicit in the (complex) incremental behaviour of the metalanguage.

## From programs to programming

Programming is the activity of modifying a program in order to bring about specific changes in its behaviour. Yet programming language theory almost exclusively focuses on the meaning of programs [22]. We outlined a 'change-oriented' viewpoint from which the meaning of a program change is a change to the program's meaning. In so doing we skipped over many difficult questions.

We raise one question now with a view to future discussion. Can we extend the change-oriented perspective to the static meaning of a program, such as its type? For example, Omar et al. [16] define a type system which incrementally maintains a proof that a program being edited is well-typed. Viewing such a system as generating a higher-order witness (explaining how specific edits induce specific changes to the type of the program) suggests a static version of our principle: the type of a program change is a change in the program's type . Equipping changes with types may improve our ability to produce useful error messages, especially if we can extend type deltas to structural reorganisations like the ones considered here.

## REFERENCES

- [1] U. A. Acar. Self-Adjusting Computation . PhD thesis, Department of Computing Science, Carnegie Mellon University, 2005.
- [2] K. Beck. Test Driven Development: By Example . Addison-Wesley Longman Publishing Company, Inc., Boston, MA, USA, 2002.
- [3] Y. Cai, P. G. Giarrusso, T. Rendel, and K. Ostermann. A theory of changes for higher-order languages: Incrementalizing λ -calculi by static differentiation. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation , PLDI '14, pp. 145-155, New York, NY, USA, 2014. ACM.
- [4] V. Donzeau-Gouge, G. Huet, B. Lang, G. Kahn, et al. Programming Environments Based on Structured Editors: The MENTOR Experience . Institut National de Recherche en Informatique et en Automatique Rocquencourt: Rapports de recherche. INRIA, 1980.
- [5] H. Ehrig, G. Engels, H.-J. Kreowski, and G. Rozenberg. Handbook of Graph Grammars and Computing by Graph Transformation: Volume 2: Applications, Languages and Tools . World Scientific, 1999.
- [6] C. Elliott. Compiling to categories. Proc. ACM Program. Lang. , 1 (ICFP):27:1-27:27, Aug 2017.
- [7] M. Fowler. Refactoring: Improving the Design of Existing Code . Addison-Wesley, Boston, MA, USA, 1999.
- [8] M. A. Hammer, Y. P. Khoo, M. Hicks, and J. S. Foster. Adapton: composable, demand-driven incremental computation. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '14 , pp. 156-166, June 2014.
- [9] M. A. Hammer, J. Dunfield, K. Headley, N. Labich, J. S. Foster, M. Hicks, and D. Van Horn. Incremental computation with names. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications , OOPSLA 2015, pp. 748-766, New York, NY, USA, 2015. ACM.
- [10] C. M. Hancock. Real-time Programming and the Big Ideas of Computational Literacy . PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 2003. AAI0805688.
- [11] C. Larman and V. R. Basili. Iterative and incremental developments. a brief history. Computer , 36(6):47-56, June 2003.
- [12] M. M. Lehman. The programming process. Technical Report IBM Research Report RC 2722, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, December 1969.
- [13] S. McDirmid. Living it up with a live programming language. In OOPSLA '07: Proceedings of the 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages,
- and Applications , pp. 623-638, New York, NY, USA, 2007. ACM.
- [14] F. McSherry, D. Murray, R. Isaacs, and M. Isard. Differential dataflow. In Proceedings of Conference on Innovative Data Systems Research (CIDR) , January 2013.
- [15] D. Michie. Memo functions and machine learning. Nature , 218: 19-22, 1968.
- [16] C. Omar, I. Voysey, M. Hilton, J. Aldrich, and M. A. Hammer. Hazelnut: A bidirectionally typed structure editor calculus. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages , POPL 2017, pp. 86-99, New York, NY, USA, 2017. ACM.
- [17] C. Omar, I. Voysey, R. Chugh, and M. A. Hammer. Live functional programming with typed holes. Proc. ACM Program. Lang. , 3 (POPL):14:1-14:32, Jan. 2019.
- [18] B. Paige and J. T. Schwartz. Expression continuity and the formal differentiation of algorithms. In Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages , POPL '77, pp. 58-71, New York, NY, USA, 1977. ACM.
- [19] R. Perera. Refactoring: to the Rubicon... and beyond! In OOPSLA '04: Companion to the 19th annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications , pp. 2-3, New York, NY, USA, 2004. ACM Press.
- [20] R. Perera. Interactive Functional Programming . PhD thesis, University of Birmingham, Birmingham, UK, July 2013. http: //etheses.bham.ac.uk/4209/.
- [21] R. Perera, U. A. Acar, J. Cheney, and P. B. Levy. Functional programs that explain their work. In Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming , ICFP '12, pp. 365-376, New York, NY, USA, 2012. ACM.
- [22] T. Petricek. Histogram: You have to know the past to understand the present, 2019. http://tomasp.net/histogram/.
- [23] D. Plump. Term graph rewriting. In H. Ehrig, G. Engels, H.-J. Kreowski, and G. Rozenberg, editors, Handbook of Graph Grammars and Computing by Graph Transformation, Volume 2: Applications, Languages and Tools , vol. 2, pp. 3-61. World Scientific Publishing, 1999.
- [24] W. Ricciotti, J. Stolarek, R. Perera, and J. Cheney. Imperative functional programs that explain their work. Proceedings of the ACM on Programming Languages , 1(ICFP):14:1-14:28, 2017.
- [25] S. L. Tanimoto. VIVA: A visual language for image processing. Journal of Visual Languages and Computing , 1(2), 1990.
- [26] T. Teitelbaum and T. Reps. The Cornell Program Synthesizer: A syntax-directed programming environment. Communications of the ACM , 24(9):563-573, Sept. 1981.
Roly Perera
The meaning of a program change is a change to the program's meaning
Programming is the activity of modifying a program in order to bring about
specific changes in its behaviour. Yet programming language theory almost
exclusively focuses on the meaning of programs. We motivate a "change-oriented"
viewpoint from which the meaning of a program change is a change to the
program's meaning.