Live CEOing Ep 735: Language Design in the Wolfram Language [DiffTools]

Let me give an intro. Okay. Hi everyone. We are here for Wolfram Language Design Review, part of our Language Completeness and Consistency series. And today we're hearing about Diff Tools, tools for diffing notebooks. So Lou, take it away.

And just by way of introduction. So Lou and I have been working on this for a long time. Me on helping Lou with the design and Lou on the implementation. What you're seeing here by long means ten years or what, several years off and on, it gets down, prioritized and such. So it's not long, like constantly. But there were hard problems here and the what we don't have every sort of visualization and interactive tool sort of cracked. So I want to set the expectations. The expectations are we believe that we've, that we've reasonably cracked all of the core algorithm and data structure problems and we have some basic visualizations as well. But, but those are things that, you know, we can continue to build out. Also, this isn't just about notebooks. This covers a lot of territory, including basic expressions. And that's kind of the simpler portion of this. So that's where Lou's going to begin. And with that I'll, I'll hand it off.

I'm waiting for this for years.

Right.

I hope. Okay, go ahead.

So here are the goals that we started with. See that, as John mentioned, some of them are notebook related, some of them are sort of generic diff related. The plan at this point is to gather what we have into a packlet. That's what I've been working on. And to release that via the packlet repo with the hope that it will eventually be, you know, these functions will eventually migrate back into the product and rather than. Well, I'll show the proposal ceremony. So there's a handful of functions that we're going to be talking about today. The thing that knows how to compare items, the thing that knows how to view that comparison, and then some convenience things built on top of that.

And in regards to the packlet repo, I mean, we would basically be ready to publish that today. But if we end up with some name changes or some structural changes coming out of this review, we don't want to create a lot of confusion by having things that change dramatically over time.

So, okay, the name Diff or a thing that's just called Diff really can't make it. People are going to get confused with differentiation and things.

I, I behemothly disagree and we can discuss that when time comes. But I have very strong arguments against your Position.

Okay, so let me, let me demonstrate what these things actually are. So we have a couple of lists. We want to understand what the differences are. Diff sort of does everything at once. It looks at these things, it compares, it boils down to the longest common subsequence using sequence alignment, and then displays a thing that has some styling associated with it. What this actually did was to create a diff object, which one can do directly with this. This is the computable representation of, of the differences between these expressions. And then using visualizing, just that object, using the viewdiff function. So diff is essentially create the object, create the difference object and show it to me. But showing it to me is not the only thing that this object is good for. You can use it, right? You can say, take this path patch and apply it to the initial list and you'll get back, you know, the new list. So this is a computable thing that can be used in interesting ways. And I've built some introspection features, so ways to get the strings out of, you know, what is the summary box. And there's a number of other properties that one can ask for or for the diff object.

That thing should surely be called summary string or something, because summary.

Okay, fine.

I mean, because one wants something which has an association that says additions three, removals one or something, or additions, deletions, whatever.

Yes, let me, I'll go ahead and take notes so you don't have to.

Thank you, John. Okay, great.

So I presume you could apply the diff object not just to A, but anything that's a superset of A. So if you try the range of 0 through 6 or whatever it is, it would, you know, do something sensible.

Well, it would do the positional replacements that, that the object represents. Right. So the object is, I'm adding an item at the beginning, I'm removing an Item at location 3, and I'm adding some things at the end or at, not at the end, at position five. So that's what this application did. So there's no guarantee if you don't apply it to the initial, to the original object. Yes, you'll get something back, maybe, but it, but, you know, whether that's a meaningful operation or not is, you know, that's, that's something that a human needs to think carefully about.

Okay.

So this is the default view for list style diffs. There are other views that one other formats for diffs and the kinds of diffs that are supported, the kind of views are supported depend on the diff object. So for list objects, these are the ones that are supported. So we can say, you know, here are the two lists as completely separate items with their items marked up. We can have sort of a more grid like view or a unified view, which is the grid like but sort of collapse into a single column. And we can invent, you know, lots of, There are lots of other things we might do here.

But. Right.

So that's, that's why, you know, it's, it's. I think it's important to have the generate the function that creates the diff object be separate from the function that views the objects because of this.

Yeah, I agree.

Richness. Okay, so that's what I wanted to demo for lists. For strings, we have a new issue because strings, you might want to compare character by character, word by word or line by line. So generatedif takes an optional third argument that determines how this, how one does this. So by default you get, you know, if you don't give a third argument, you just get character by character view. And the viewing shows you, you know, sort of splits words and somewhat difficult to read when the characters happen to be prose. This maybe is slightly easier to read. And of course strings might come from other places too. If you have peptide sequence, for instance, there's a view where it shows in a. More, you know, this is a view that you might see in biology.

Right.

So that's character by character. If you specify words as the third argument to generate diff or to diff, then the, you know, the granularity is word. It's a bit easier to make sense of what the edit was. And if the string covers multiple lines the then well, this is starting to look like a file. So this is an important case for comparing text files. But I'll start off with just text strings. We have, you know, range of 10. And here we have added a couple and we've removed a couple of things and by default we get the side by side view where.

And is the information more or less the same? So if we, if we opened up that summary box, we would see, you know, at this lines and that line.

Correct.

So this does not carry any context like you know, what, what a git diff would where it says not only where I'm adding it, but sort of what's the nearby stuff? So I know that I am meaningful.

Well, so the nearby stuff is included and I will. If we look at the input form of this, the nearby stuff is in fact stored in the changes object. So here we have a Difference. Here we have a run of identical elements. And here we have difference and a run of identical elements. Now, these identical elements might be really long. So there are, you know, if this was more than six, you know, I would. There would be a lesion here by default, which you could override. But if I were to change. Well, let's see. Do I want to change this on the fly here to 30 and 32 and look at the input form of that. We'll see that, you know, there are these elisions. You know, I'm not carrying around every bit of context, but one could. And there's an example of that down in the options section below.

Right.

And again, so we have the default view for these guys. We have a unified view. And shortly, when we talk about text files, it'll be important to have, you know, a numbered view where the numbers correspond to, you know, the first. The first column is the first element and the second column, line numbers, corresponds to the numbering of the second element.

Is that 18 skeleton one of those more matches?

That's correct, because I am now working on an object that I. That. Yes. Where did I do that? So I did set that to obj. So the more matches becomes elision. And not sure what, if anything, different this shows, but there we go for strings for text files.

So what that shows is, you know, what happens if you have a change in addition to. Right, so we have a purple there.

Right.

Because I changed 5 to 50 rather than deleting it outright.

Right.

There are some default stylings. Green, red, blue. These are adjustable, but I'm not sure that. I mean, we can talk about that later. But they are adjustable. And for text files, I found a couple of files in the layout that are remarkably similar. Looks like they were possibly created by the same person at the same time and just sort of editing things a little bit. So, you know, a real world example of text file diffing. All right, so all that's fairly straightforward. Now let's look at notebooks. The way that notebooks are handled. Notebooks can. We can look at. We can feed these guys notebook expressions, notebook objects, notebook files. Of course, when you give a notebook file, it needs to be wrapped in a file wrapper because otherwise it could be treated as a string. So that's an important aspect of syntax. And then the diffuser compares the list of cells and those are aligned by virtue of looking at their expression uuids. This is especially interesting in the case of source control, where you have edits to the same file, the literal same file with the same UUIDs over time. And so the UUIDs for those cell objects are an important aspect of, you know, aligning these, these diffs. And then cell grouping and notebook options are somewhat easier to handle. So here are a couple of simple notebooks. You could probably figure out the diffs just by looking at these, but I'm going to pop them up on the screen here.

Okay.

So you can again probably see the differences, but I want to show the report that diff creates by default. And this is it. So we've given it to notebook expressions. In the content, there are two things that happened. The title cell has changed in some way. If we open this up, we see a sort of summary of what that change looks like. And we have a new cell appearing in the second notebook. So this report is the default view for notebook differencing. And in addition, you see the notebook objects, the, sorry, the notebook options, and the diff object is included just for people who know how to handle diff objects. I'm not sure that this is going to appear in the final version of this. We might just extract the summary string or maybe some other summary bits and plop them up at the top here as a, as a top sheet of what the changes are. All right, I'll press on.

So that's interesting, but awfully verbose. We'll come back to this. That's right.

Well, well, and, and, and, and I think, you know, I mean, that report, that's the sort of thing that I totally expect that will at some point, not necessarily today, but at some point want to grind down further to, you know, to, to better optimize how humans can take it in.

Absolutely. And it's not very interactive either. One wants an interactive thing. And this example is going to show slightly better interactivity here. I've grabbed two, two CVS commits of a particular documentation source notebook to compare them, and I've trimmed them down just to keep the file size of this agenda notebook small. And if we look at this now, it's not so simple just looking at these guys. There's an addition, a removal, and some edits. Good luck finding them and good luck having a text diff showing you what they are. But here we have a view that shows what they are. And when diffing notebook objects, there's now these links saying, a note cell has changed. I click here and we've scrolled down to the notebooks to the cell that has changed. And now you might have a chance at visually inspecting the differences. Or you can pop this guy open and see.

Ah, okay.

Looks like somebody removed parentheses and likewise for a removed cell. Okay, so there's a cell that was removed. That was the removed cell and that's where it would have been Note cell changed Again, it looks like parens and parens. So these commits had to do with parens.

Why does it say notes? Is that because that's the style of those cells?

Yes, yes, sorry. There. These disks are all, all happen to be in style in cells whose style are notes. It was an accident of the choice of example. And here we have a cell that was added after the last cell in this notebook. So now again, there's, this is limited interactivity. One very much wants to say, you know, take these two notebooks and create a new notebook by grabbing some diffs. You know, I want, I want to accept this change, I want to reject this removal, etc. And that's something that we have the kernel features for, we don't have the interface for just yet.

Okay, right.

So, and then I had some sort of summarized abbreviated views of the same object to give you a more visceral sense of what the diffs are. So here is a sort of whimsical view of, you know, cells that are the same or white cells that are edited are blue remove. Yeah, you get the idea. And likewise a thing that shows, you know, here are the cells you started with, here are the ones you finished with and this is what happened in the meantime. So here we have a cell that didn't exist that now does. Cell that didn't. That did exist and now doesn't. And some edits. And depending on the size of the notebook, number of cells, these might be useful visualizations and there's probably lots more. Right, so and then, I mean those.

Could also interact with the notebook history stuff.

They could, they could be interactive, they could, they could interact with.

Well, no, but I mean they also could indicate how old the cell was and things.

Sorry, by interact you mean this kind of visualization? Yeah.

Could be informed by notebook history.

Yeah, I agree. Yes, we could give special attention to cell change times in these visualizations. Yes, right. So, and in this report we've already seen what I'm doing for cell differencing, but I'll give a little bit more detail on cell differencing directly. Of course we have cell cell object and the cell generators. These are all supported by the functions diff and generatedif track differences in format, type and the contents. The contents of a cell are broken down into string tokens. This is true in both text data and box data. And then those are compared as a flat list and then restyled. Right. So I don't dig. We don't have sort of recursive differencing in typesetting just yet. We have sort of a. This is a flat. The Robox is. Is taken as a flat list. And I'll show, I'll show. I'll. I'll demonstrate that in a second. So here's a couple of cells extracted from various points in the history of a manipulate guide page. And this is. The differences between them should be clear. The cell style didn't change, some of the options changed, some of the contents changed.

Right.

And for box data here, I'm just going to evaluate a couple of integrals. So you have a couple output cells here. I'm going to grab the cell object.

Sorry, sorry, Lou, back on the text case. So you are choosing words as the default view. Effectively, this is equivalent to the string words. Correct.

The token. I'm tokenizing this as strings. Yes. Which for textiles seem like the natural thing to do.

Yeah, but. But not just strings, but as.

Sorry, sorry.

As words. Specifically words.

Yes.

I misspoke.

Okay, right.

So let's grab the cell objects for the previous output and the output before that one. So we.

Oops.

So we have C1, C2 are now these output cells and we compare them and we see that the difference engine thinks that there were four edits. What were they? So we have X root root X plus X root negative root X plus X. As I said, these are not recursive yet. So this could go into the square root box and determine that the difference was sort of more isolated. It doesn't yet. That will be some work. And you know, other things are highlighted in green and red. Some of these things, I mean, one of the things I'm concerned about is when the differences are small. You know, this is a very small sliver of color to distinguish.

We should make the colors bigger. We should make it a blog. A quad that has the minus sign inside it could be a minimum size for the box.

Okay, yeah, that's a good idea. But other visualizations of these cell differences, we could look at just the contents, which just is exactly what you see here, but without the paraphernalia. I tried my hand at, you know, recombining these things and showing the differences next to one another. Maybe above one another would have been slightly clearer.

I think above would be better.

Yeah. And likewise, there's a view that lets you not just get the changes object but sort of a digested version of the computable data so that you can have other, you know, so somebody can digest this form and extract it and use it in their own interface or their own whatever. Sort of exposing a bit of the implementation of the cell differencing.

Right.

So, and as John pointed out at the beginning, you know, now that we have cell differencing, this is really, you know, arbitrary expressions can appear in cells. So we have arbitrary expression differencing as well. I have some convenience arguments for that. So we have, you know, here's, here's an argument that says, all right, coerce these things to their input form strings and compare them as strings. This is coerce them to standard form cells and compare them as cells. So I expect these to be sort of the high level versions of things that people generally want when comparing expressions. Okay, so there's one other kind of diff that's important for source control and that is a three way diff where you have an original and you have two different people who have edited this thing in two different ways and you need to merge them back together. And sometimes that's possible and sometimes there's a conflict. We don't have a function that does this alignment in Wolfram language yet I've written one, multi alignment, which is essentially an extension of sequence alignment that allows these.

Is that the right name for it? I mean, multiple sequence alignment in biology means something completely different.

I didn't know that.

Yeah.

And I do not have a strong opinion on this.

On the name.

On the name.

Yeah, I don't think that's the right name.

Okay, be that as it may, here is how it works. So we have an original expression, we have one person edited it to add something if beginning and the end, we have another person who edited it to do other things. And we see this completely opaque multi alignment with lots of nested lists and to visualize it. So generatedif uses notebook alignment. The syntax that I've chosen for now to keep this to be two arguments is to have the original. And then when you give a list of two different.

I don't understand how two different. I mean, but how does generate diff not just think it's. If a rig was a list, I, I'm just completely.

Right, this is.

Okay, so there is, there is a difficulty here where a list a pair in the second argument is meaningful. Maybe we need to have this be another argument or can't work that way.

Okay.

But for now this has noticed that the multi alignment carries information about additions, removal And a conflict. And then we view that and we see, ok, we see the addition. There's an addition, there was a removal, but somebody. So this guy added two things after the original. This guy added something after the original as well. So there's no way by default to know where these should be with regard to one another. So that's conflict. And this is very common in source control to have merging tools. The goal here is to eventually have some Wolfram language scripts that could be attached to that you could set up as an external diffing utility for your git clients, Mercurial client, CBS client, et cetera, so that this would all just work, go into the Wolfram technology stack and you know, either do the merging or provide some information about why it can't.

Now, is there a way to do that kind of call out from Git?

Well, Git clients tend to have ways to do that. Yes.

I don't get. Git has a way to hook into external tools. So they have. There's a thing called a Git diff tool and a thing called a Git merge tool. And this is basically git providing a bunch of standardized information to a tool of your choice where you can then use that tool to resolve, to either visualize or resolve as the case may be the conflict.

Right, so Wolfram language script is really the, the only possible way of tying into. Well, it's our best. It's our best solution for tying into that, I think. Ok, so right, so those are the functions. There are a couple palettes I built on top of those functions. Since I have the packlet installed, I have those palettes here for comparing cells in place. So here, let me. Okay. And for comparing notebooks as well. This actually was very useful. In the last hour, Itai and I were going back and forth with edits to this Agenda notebook and we were editing it simultaneously. And so it was my job to, you know, sort of merge Etai's edits back into what I was working on. So this was a very. This, you know, has real world street cred already anyway. And I've also built out a thing that actually it's been in Stash link for a while. There's a utility for extracting a file out of a one of our stash.wolfram.com repos and comparing, you know, one branch against another. So you can see, you know, what happened to Core between our previous release and our current setup or whatever. So this is going to be very useful internally. It might be something that we can package up in a way for external folks. But.

Right, so that's coming something that's not represented here. It's in the kind of more tools to build on top of this. But one of the things which we have done in Gitlink is we've said so Gitlink is still operating in the world of line by line diffs only. But it's not just operating on notebooks, it's operating on all kinds of files. And we've said in some cases when there is a git conflict, try this strategy for merging it. And the strategy might be a line by line strategy. For example, if we know the file is a bunch of messages and there might oftentimes be conflicts because someone adds message A to the end of the list and someone else adds message B to the end of the list. Well just take both and the order doesn't even matter. That's a strategy. And then if it's a notebook, forget the line by line diffs for certain kinds of notebooks. You can just process it as a notebook file. And we do this in for style sheets, for example, so that changes to say core mb. We can have multiple changes and Gitlink and figure it out. So I, you know, some of those strategies we've already thought about for Gitlink I think, you know, can evolve from the work here as well.

All right, let's. Let's not look at the options yet. Okay? Right, okay. This is great. You know, waiting for it for 20 years or more. Let's start in on some of the issues. By the way, let me, let me. Perhaps you can unshare for a second. Let me show you something just for amusement. Oh for goodness sake. Sorry, I'm just have to rearrange something here. Oh my gosh. Too many things. Okay, Okay. It might amuse you. Something I was literally just working on yesterday. This is, this is multi way evaluation paths. Notice these objects here. See what they are? They're basically the diffs of expressions.

Interesting.

I mean I'm not vertical.

Yes.

Yeah, they're vertical. I mean this formatting is not right yet. But these are just to understand what this is because it's, you know, the evaluator is basically going. Well actually this is a multi way evaluator. So this is a more sophisticated thing. But it's going from an expression through an event, which is the diff basically to another expression. See what I'm saying? So in a sense, you know the whole story. You can think of the evaluator as being you. You could imagine running Your diffs on the before and after for the evaluator and you will get an event which corresponds to the diffuser. See what I'm saying? Yep. Just an FYI. Okay, back to your, back to your screen. Okay, let's dig in here. Okay. All right, so generate diff. All right, so first of all, I mean, don't. I'm sure you're doing this, but in the diff object, you obviously should version the diff object so that, you know, we can put all kinds of weird stuff into the diff object and one day we might change our diff objects, but we don't want all the old diff objects to become, you know, to become bad. Right.

I don't think I am, but that's an excellent idea.

Okay, yeah, so you need to put something in there for, you know, whatever. Yeah, or diff version or something. Okay, so then. All right, so hold on a second. Generate diff. Okay, now you're saying how are you diffing, right, that third element, that third argument.

Right. What are you caring about?

Right. By the way, I suspect that this three way diff probably should be a separate function maybe because I think it's going to need different options in the end. But anyway, the, the, the. What are you caring about? So the list you have right now, which sort of reminds me of import formats and. Or it reminds me of word count, character count, etc. You know what I'm saying? So can you show the list of elements that you have now for generic diff?

It depends. Let's see. Can I. Yes, I think I can. Hold on, let me look at sources.

And then we need an analogy to this. And I suspect the analogy is the importer. Anybody got comments on that? Worst characters.

Characters is misnamed strings in this list.

Okay, so it should be called characters. Yep. And I don't understand what lists means. Is that list elements or what?

Yes, it means list elements as opposed to cell lists which have, you know, sort of special handling.

Let's be clear what these things are. These are the unit, the granularity of, of. Of comparison. Right?

Well, not exactly granularity, but. Right, because like input form, standard form, it's like.

Okay, but then that, then that's not the right thing there. I mean, most of these, I mean, maybe we can elide this list to include some of those. But in a first approximation, I would assume this is diff by character, diff by line, diff by word. Right.

And it's also diff by input form.

No, but it's Then diff by input form by character, Diff by input form by something else.

Right, that's correct. Yeah.

Right. So I, you know. Well, look, I think. Okay, so let me make a suggestion here. So could you get that list again? Okay, so let's just go through what that list actually means. All right, the first thing is, is it just a list? Or if I have F of A, B, C, F of abd or something, does it do the same thing there?

It will not, for. It will say, I can't do that. So there. There are only. Some expressions are supported by default. We could go straight to one of the, you know, renderings.

Like, if you have two polynomials, it might make perfect sense to do a diff. Okay, but, but so what you're saying.

Is a diff of what, though?

Of the.

Of the full form, of the input form, of the standard form. That's the. That's the point.

Well, I think that's the point, that the diff actually is a semantic diff. In that case, more semantic. Okay, let's just go through these and understand what they are. Okay, the first thing is list elements, basically.

Correct.

Can we make some notes? Maybe on your left hand side. Don't, don't. Whatever. Wherever you want.

Fine. John was taking notes, but sure.

But just, Just make it. Could you not obscure that thing?

Stephen, let me do one thing at a time, please.

Yeah, okay, sorry. All right, no matter. I have many questions. This is very wonderful stuff. I have many questions. Okay, so that first thing is list elements. Right. The second thing is characters. The third thing genuinely is lines. Right.

It's. As long as you understand it's lines of text.

Well, then write comment. Text lines, then. No, just text lines. Text lines. One word. Text lines.

I'm getting there.

Yeah. Okay. Okay, okay, okay. Sorry. Okay. Words. All right. What's notebooks? What does that mean?

That's the diff object that represents when you're comparing full. A full notebook against another full notebook.

But what granularity are you comparing with?

It's. It's essentially the granularity of the cell for the contents, but it's also comparing notebook options as well.

Okay, so I can imagine, you know, let's say you have F of ABC and G of abc. There's not what you've covered in lists, but you might have something where you are comparing expressions. Yeah. You know, there's several other people who are. Who are might be relevant for this meeting. Like Nick might be relevant because he's been working on a bunch of these things. Christopher might be Relevant other people. Several other people might be relevant and. And should probably be asked about this stuff at some point.

No, I mean, Christopher is optional for this meeting. He has chosen not to show up.

But maybe somebody should ping him and tell him what we're talking about. About he might show up. Somebody do that, please.

Yeah.

Is Nicholas is optional for this meeting, which Nick me.

No, because we were told he cannot be in any meetings.

That's not right. It's the confusion. Somebody was confused. Very confused. No matter. Very, very confused. Okay, Take that separately offline. Okay. Okay. Cell lists, what does that mean?

So this, the distinction between cell list and cells is, you know, this is one cell versus another cell and this is the list of cells from a notebook. This is the cells part of the. Of what is doing. It's the first notebook.

Okay, what does input form mean? Is that character by character? Input form.

It is character by character. Yes.

Right.

Because for what I mean, you could maybe possibly token by being words, but lines does not make sense for input.

Form because it could be token.

Lines.

Could be tokens. Yes, could be tokens.

It could be tokens.

All right, so can you make a note there? That's either characters or tokens. Now, standard form. Characters is pretty funky for standard form, isn't it? I mean, that's mostly tokens.

Well, currently it's only tokens, right?

Yeah.

Right.

That's basically stick the standard form in the cell and diff to cell.

Correct. Which uses the tokens that I was describing.

Okay, so I'm just, I'm just, I'm just looking at these. Okay, so hold on, hold on, hold on. So first thing is, these are a mess and we need to figure out how to get these better. But I do understand the value of having a diff with respect to something. Okay. Okay, then we've got the three way diff, which is rather obscurely to me, generating a diff object. I don't know why it's generating a diff object rather than a diff3 object or something, you know, I mean, how common is a three way diff and is it, would it make sense to say, you know, generate diff, you know, a diff2 and a diff3 object. For example.

Christopher is here.

Okay. Hey, Christopher, this is. We're talking about a general diff capability for expressions, notebooks, files, etc. They had a long.

Right.

Although I thought.

Okay, so there's actually. Because, I mean, expression diffing has been like every one of these categories, expression diffing and notebook dipping have Both been like these, these Holy Grail.

Okay. The Holy Grail has now been captured and Lou has.

Okay, great.

I mean, I, I wouldn't say that general expression diffing, but if you're willing to, you know, look at in its, you know, input form or standard form, then we have general expression diffing. Beyond that we have lists, strings, cells and notebooks.

Yeah, I was jumping in to say exactly the same thing. So.

But to your question, Steven, of how common are three way diffs, I think in the context of source control, they're extremely common. Outside of source control, they're probably not.

At all for Christmas benefit. Just open up one thing where you're showing a cool picture of a diff that's happened just, just to give some sense of what's here.

Sure.

There. Okay.

Oh, nice.

So it's quite developed, but needs polishing.

And also show Christopher the box, the standard form boxes. The.

That's what. Well, okay, Right.

Okay.

That's in the cells, I think. It's in the cells, yeah.

Oh, still generated.

There you go.

So nice. I'll repeat, it's not a full recursive diff. So for instance, the square, this outer square root box isn't in fact different from one to the other, but for now these are treated as sort of flat lists of tokens.

Incidentally, I don't know whether you've. I mean, I know at the summer school several years ago, somebody did a quite extensive project on tree diffing.

We looked at it.

Okay.

Lou looked at it more than I did. I don't remember what assessment we came to.

Frankly, I don't remember either.

But.

We were aware it wasn't so much stuff that we thought that we could use. Right.

I mean, I think if I remember right, I mean there have been several different projects at summer school, I think over many years. But like the usual problem is that they end up with the, the like being very fine grained. So like if you give it. I mean this is a right. It's like for example, in text stiffing you. You can see this as well in like kind of not very good algorithms, which is like if you give two pieces of just unrelated text and the correct thing is to say you deleted one piece of text and replaced it to another. But instead it says, well actually this space was actually kept. And you know, this space was, was actually not changed. But, but you know, all the letters around it were. And, and you can kind of like cobble together one string from another and I don't know, there are A lot of problems, to be clear, it's more of a heuristic thing than a purely mathematical.

Sequence alignment hopefully has taken care of some of that for strings. And not being stupid like that. I don't know, I'm not sure.

And I'm not sure it should necessarily, because I feel like once you start, kind of a lot of that's kind of more heuristic stuff that's useful for humans looking at diffs, but isn't. Otherwise.

Yeah, I will say my work is built on sequence alignment, which has options. And if there are certain values of these options that are better for strings than other values, then I would very much like to learn about that so that I could use it automatically.

You should find that out. I don't know the answer. I mean, maybe the bioinformatics folk will know something about that. Okay, all right, let's. Let's go back up here. So the thing we were talking about, let's go through the survey of what we have to look at from a design point of view. So first thing is the granularity of the diff. And you know, we've still got a bit of a mess here with how we specify those granularities. I mean, that. That is the right way to think about this. It's granularity. Well, both, actually. It's two things. It's the granularity and the target of the diff. Okay, but what do I mean by target? That is, is it the list of cells in a notebook, or does it include the notebook options themselves, you know, as well, that type of thing. Right. So there's two different issues here. Is it, you know, are we looking at character by character or word by word or line by line? And are we looking at certain kinds of metadata? So, for example, you could imagine a diff here, an image diff, for instance. Right. And the image diff might or might not look at the xif. Am I making sense? Right. Yes. So there's really two issues, granularity and target, I believe. Is there anything else here that you're. Oh, and. And there's another one, which is filtering, which is input form, standard form, traditional form. So there's granularity, target and filtering. Could you make.

I would call this coercion rather than filtering.

Okay, fine.

On fingers.

Is it really coercion? I mean, in other words, if one of them. But it's to both of them. Right. So it's not.

This was just syntactic sugar on top of a thing that you could already get without these. Right.

You could give an option or what?

Well, no, you could just say generate diff of two string of expression comma input form, two string of another expression comma input form.

I see, I see. Okay.

All right.

The first thing is. Yeah, yeah, you get it. Okay, so the second syntactic issue we have is the 3 way diff. I think that should be generate diff3 or something like that. Because I think that there's no way to untangle that syntax mess of having two plus also. Is there a four way diff?

Not usually.

Yeah, but I mean, is it something we can imagine or is it.

So git has a multi merge. I think they call it an octomergen storage facility. But. Well, it's the sort of thing that, I mean, people care deeply that it works, but nobody understands what it does, except for, you know, true domain experts.

But what they care about is the merge. Right. For that, from that diff.

Right, right.

Okay, so. Okay, so we've got this, We've got view diff, which we're going to talk about. I'm not sure that name is right. We don't have a lot of other views in the system, but that's the diff format. That's the. That's showing diffs in different ways with colored backgrounds and this, that and the other. And. But generate diffusion generates a diff object. That. Okay, so when you say apply a diff, there's no point in applying a diff to the thing you just diff'd, right? You're applying a diff to something different, to something where, I mean, my God, it reminds me.

Or you're sending. Or you're sending the patch to someone else to apply it to the same thing.

I know.

I'm remembering when I first used a timeshared computer system in 1976, everything was based on patch files for some reason of saving storage. Right. They didn't want, you know, program files and so on to be replicated. And so everything was in a patch.

That was the same thing with. This is also the way that CVS and before it, rcs.

Yes, before it, the thing that I think I was using in 1976, it's.

It's not.

In 1976, it was probably SCCS.

I think that might have even been more modern than this. It was. I remember that the CDC computers had a whole fancy version of this. Anyway, no matter.

So as. As a point of interest, it's not the core, the core model upon which Git operates. Now, there are some implementational details that Kind of fudge what the. What the operating model should be. But. But in Princ, the way Git operates is you actually have a complete and separate copy of each and every iteration. Of course, if copies happen to be identical, then you don't get multiple copies because of content addressability.

Well, it's because Git was developed long after all these other systems and when storage was much cheaper.

Yeah, and it was developed by someone who thought, you know, who had expertise in file systems, and he designed Git as if it were a file system.

That's an interesting statement.

And I mean, you know, I'm not making, you know, a genius meta analysis. I mean, he's. He's said as much.

Okay, but so. So to what extent are we adopting the CVS model instead of the Git model here in some way? Or is that not how I should think about it? I mean, we're imagining. We're imagining a typical workflow is. Okay, so let's give an example of like blogs I write which have a source, and then maybe they were already converted into some other form, and then I make a change and somebody needs to diff it. And I believe we have some tools that do that right now. But this will be a better version of those tools. Right?

Idea.

Yeah.

Yeah. Soren on our live stream is commenting. Maybe it should be diff, generate, diff, view, etc. Rather than having diff second. That's a. I was going to bring up a similar thing.

I. I have to admit I'm. I'm still a little weak on our general principles of when we use object, verb or versus verb Object.

I'm afraid.

I'm.

I am too. I mean, it's been. You know, there's some cases which are anchored well.

Darn it. Because I was depending on you.

No, I. I definitely have a feeling for this. But I mean, there are some anchor cases where it's clear it has to be one way around or the other. But then there is sort of we're stringing things in the middle and those are a little bit less clear.

Okay.

I think what we often do, but I'll claim we often do is, is it's usually noun verb, if nothing else to make autocomplete nicer. But then it's only verb noun for certain things that like that are consistent like that are always there, like constructors. Like if it's create. Blah. Create first, usually. But then any operations will be noun verb.

So it's sort of certain privileged verbs that tend to want to be first.

Right. Is Your correct. Yes, I think that's my argument. Way to put it. In which case this would be definitively diff generate.

Well, wait, unless it's. Unless generate or create is sort of a privileged verb.

I'm not sure.

Well, create diff is a primary privileged one.

We do have things like generate symmetric key.

Oh, that's true, we do. Yes, we do. So generate is possible, but view we've never had.

Right.

Then that would be diff view or something.

Yeah, but we can't have generate diff and diff view. That's unrememberable. Okay, let's, let's continue here for a second with. So that's, that's the thing we need to consider. But now. Okay, I mean, I'm kind of feeling like. Is the diff object that you get from a three way diff, is it a different. It's different from a two way diff, isn't it? The diff the diff object thing.

Well, it has different contents.

Well, that means it's different.

Well, no, I mean it has the same it here. I mean it's the same structure. It's just instead of a. The changes list, instead of each element having a pair, when the things are. When there's a difference, it's a triple.

Right.

And then.

And so I, I think Lou's reticence here is saying.

Reluctant. I'm describing.

Well, a potential reticence is analogizing to. For example, you have point in 2D objects and point in 3D objects which are in a way fundamentally different, but in a way quite similar.

Yeah, right. Okay, so you're saying we could have a list. I mean, if we were doing the octopus diffuse, whatever it is, that in principle that structure could be octopused, so to speak. It could be a 4 way diff as well. That structure doesn't. Doesn't limit it three way.

Correct.

Yes.

Okay, but now apply diff if you've given a 3 a 3 way diff object. If your object is a 3 way diff object, what the heck does apply.

Diff.It would effectively be a merge, right? It. It takes the original and it applies both. It applies both sets of edits as long as there is no conflicting edit.

I see. So it's a union. It's a diff union. Unless there's a. I mean in practice apply diff with a three way diff object. If there was a merge conflict diff, you know, a conflict, then it would just get an error message and fail. Correct.

But, but apply diff could also be the, the container by which you express a conflict resolution strategy which we don't yet have here.

Is that true?

Correct.

We have in Gitlink, but we don't yet have here.

Yeah, but the conflict strategy could be, you know, Jim always wins type thing or something.

Yes. I mean the most trivial strategies which are useful in certain contexts is left side always wins, right side always wins or you know, merge or take both. You know, kind of take both if you can. Yeah. And.

Right.

Okay.

But I think you're right Stephen, in that apply diff or whatever we call it is really most interesting in the, in this case, in the three way merge case. In the two way case it's, it's a, it's. Unless you're sending patches around, it's a trivial. You know, you probably would never need this.

But, but, but that is useful. I mean one of the, one of the core use cases for certain git users, I mean, you know, not as much for your kind of average everyday git user but, but this was a core use case in Linux is being able to send around patch files.

Well, I know that was the core use case in 1976 as well, but do we have a use case with patch files?

Well, actually we do.

Let me give you a scenario. Okay, so somebody has written a. Well, maybe.

Well, I could certainly imagine, you know, a programmatic use, right. Where you're like apply the change. I can infer from here to these other guys.

Yes. Well, I'm, I'm, I was thinking I have a function that I've written. Somebody has a change, they tell me to that function. Okay, here's a question. I, I don't think this is plausible. No, it's not going to work. I mean if it's like I've got these functions and I've changed the way that I'm doing options or error handling in these functions. There's no way I can specify that with diffs. No way. This is much more, much too close to literal.

I mean I wouldn't say no way, but I would agree that it's impractical.

Yeah, I mean this, the apply diff for a two way diff is, is primarily the, you know, 50 year old patch file idea.

Yeah.

Which seems to me like it doesn't have a great use in modern times. Okay, now multi alignment. Okay, one comment about.

So I mean, you know, the big use case in Linux development is when you're dealing with multiple contributors. So it's not just you know, person A feeding a patch to person B. It's you know, persons A1, A2, A3 and A4 all feeding interesting, but different patches to person B. I see.

And when they don't conflict, I mean, well, but you apply a patch, then you apply another patch and because the patches, because the diff objects have enough context, they can be. They're non conflict. You know, it's so bizarre.

I mean, I mean there's no guarantee of non confliction, but it can happen quite often though.

I know what's so bizarre is this is so similar to these. This is the difference between space like separation and branch like separation. In our physics project terms, space like separation is things happen at different places in space and they happen independently. Branch like separation means things happen on two different branches in history, perhaps at the same place. So that's what you're describing. So long as it's space like separated, you're all good. You can apply the diffs. If it's branch like separated, they have a conflict. So I see. So, so basically many space like separated diffs are in other words, not. But I think it's not a totally useless way to say it because it means that they're diffs two different to different places, basically.

Yes, yes, right, yes, right.

And in fact, you know, to, you know the situation with Linux that John was describing, it's really, you have A11 through A1N sending to B1 and then you know, A21 through A2M sending to B2, etc. And you know, enough chains of this up to, you know, Linus and he, you know, he applies the mega patches that were sort of created by unioning in previous stages.

So do we have a patch unioning system that will be multiple diff objects that are being union into a single diff object?

Right. It's. We, we don't have a diff object algebra in that regard, but I don't think it's insane to make one.

Okay.

I, you know, I mean, you know, we have to question what directions are the most valuable to proceed.

Yeah, I understand, but that's plausible. Right, but so to some extent merge, the function merge that is used for associations has also a way of dealing with conflicts. Right. If you look up merge documentation for merge, somewhat unsurprisingly. Yeah. Supplied to list of values that share the same key. So that's the, that's the precedent we have for how a merge could be done. Right. So I mean in your leftmost, rightmost, it's either first, last, whatever else. Is that right? I mean, is that, does that make sense? That's, that's the, that is the, the conflict resolution function. Yeah, yeah, it's a conflict resolution function for Apply Diff, which is in gitlink.

What we did, we express it as an option and that option takes certain string values.

That makes sense.

I mean it can take a RAW function as well. But the string values were, are the common cases for which, you know, we have the functionality embedded therein.

Yeah, it makes sense. I think that's the right way to do it. Okay, can we go back. Sorry to the left hand side. If you remove that, that thing. Okay. This multi alignment, which I think cannot. I mean I believe in bioinformatics that really means something different. But you have to ask, you know, sequence alignment does not produce the most beautiful output. It is readable. You know, we've had, there was a summer school project I think to make a pretty printer for sequence alignment, which I'm pretty sure is in the function repository. But what you're providing here should be, you know, view diff. You had applicable to a RAW sequence alignment output, didn't you? Yes, you did because you showed a bioinformatics example.

It wasn't directly to sequence alignment. I mean I'm using SQL alignment behind the scenes to do this alignment.

Right, but you should be able to take a sequence alignment output and visualize it using, you know, use. Using this. It's just a minor convenience. Now you know, you got to understand I don't know how sequence alignment is. I mean again there are all kinds of biology specific heuristics that get, you know, packaged up into things like blast. Although that works, that's slightly different, that's a matching thing, but okay. I mean, and you know, in the bioinformatics world there's the sort of the indels, you know, this concept of indel, insertion, deletion, indel and substitution as being the. Which is also what you're using here. Insertion, deletion, substitution. Right.

Well, I'm using it because sequence alignment uses it, but.

Yes, no, I understand that but I mean the basic operation, because in biology another operation is two things got flipped around which you're not or copy number changes, you know, which I don't think is relevant for this, although it's worth bearing that in mind.

Yeah, it should be said that, you know, I mean elsewhere those are operations that, that, that I think lots of people would like to see in diff outputs generally. But I'm not aware of any broad based diffing type of tool that actually works doing those kinds of operations.

Okay.

I would, I would love to see A got flipped with B, but nobody's doing that. Probably because it's quite hard.

I don't guarantee it's that hard because it's done in bioinformatics. Right. Although it may not. I mean that may be non trivial algorithms. I don't really know.

And it's all.

Well, that's also a very limited, you know, Alphabet.

Yeah, that might help. That might help. There are definitely string algorithms which will use hashing where that would help.

And you know, part of what makes it hard is oh, it got flipped, but then it got flipped, flipped and then minor modifications made sure.

But we should look whether there are algorithms for that. But that's a future enhancement. That's definitely not for right now, but whatever. Look, sequence alignment, okay. There is a thing, multiple sequence alignment. Okay. Which is used. It's like the, the precursor to those, to protein folding. The old, the, the pre, the last few months protein folding technology. I don't know exactly what that I, I've seen the outputs from those things and they're, they are, you know, what you would expect. There are multiple versions of, of sequence. You've got to ask somebody how this works and maybe in fact it is the concept you want. It might actually be a concept you want. Want. I'm not sure.

Okay, so are you suggesting if it's the concept we want, then maybe the name is appropriate?

Yes. But then, then it's got to be an N way thing because that's actually useful. And I, I, I think you might find our bioinfox team has actually been building this. As I say, it is. It is. What's that?

Even better.

Yeah.

If it's built. Yeah.

Yeah. Okay, so now, okay, so we have to straighten out this granularities business.

Sorry, who's, who's the point person for.

Oh, you could ask Michael. You can start with Michael. He won't be the actual person, but start with Michael. There's a new person who's working on this stuff is probably the right person, but. Okay. I have to go somewhere else soon here and this. We should set up another custom meeting about this topic. But. Okay.

You want to talk about diff. On its own at all.

The function as in.

Well, the name. Because at the beginning you had some concerns.

Well, about differentiation. I might. My concerns about differentiation are melting.

Okay.

What do you think about that?

So remember we had this discussion not so long ago about, about the option that is used for, for coding ligatures and at the time you talked me down from. I Don't remember what the name was, but a name that used to the, you know, the term ligature and, and talk me into something else. And now I have to keep reminding you what the name of that option is. Yes, because you keep asking what is the name of the option that does coding ligatures?

What is the name anyway? Auto Operator.

It's Operator appearances.

Okay.

Not up. It's not automatic operator rendering.

Oh, sorry. It might be auto operator renderings.

That's what I think. Something like that.

Yes. My object lesson in not backing down when the world has a really standardized name for this.

Well, except the coding Ligatures is not a standard name.

It kind of is. You're using it all the time. Because that's another name for it.

I know, I know, I know. It's one of these names which once invented, turns out to be the right name.

Yeah.

And I agree that diff is, is a very generic name. So fine. I mean, I think it's a now, you know. Okay, so I don't understand why Diff doesn't have a print form. I mean, is the output of diff is the output view diff? I don't even understand why there is a view diff. Why doesn't a diff object just display as by default, as a diff?

Well, I mean, ultimately I think that it's going to be very useful to specify different ways of viewing diffs. I agree, and I certainly don't think that we want to encourage people to do that by rerunning the diff all over again.

No, I agree. So what I'm suggesting is this, okay, you run the diffuser with diff or something. Okay. And it produces for you, let's say diff is the, is the main function that actually is the active function. Diff produces a diff object, Diff object formats as a viewed diff and you can tell it different. And then we have another, you know, a possibly like we do with show and things like this. I don't know whether this works with the argument structure, but possibly something like this isn't quite right. But what we would do in other cases, we would basically say diff again on the diff object comma format.

Well, this won't work with notebook objects. Right. Because the view is something that doesn't live in the notebook.

Okay.

And you know, hold on, hold on, hold on. I think it's also quite unyieldy to you know, write, you know, copy this enormous looking thing instead of a small summary box to say, oh, I. And when you want to say, oh, I want to view this some other way.

Well, the other thing we've done for the notebook case is, which we've done for notebook objects and so on. Is it. Is it a summary box? But it has an opener arrow.

Right.

What you get in the notebook is, is just the summary box, but you click a button in it to open it as a separate notebook. Do you see what I'm saying?

Yeah.

We've got more to grind on this. Okay. We're going to get a. This is. We're close, but we're not. This isn't right yet. There's a way of doing this, I think, where you just. Where. Basically, here's what happens. You type diff, you get a diff object. The diff object displays as a reasonable formatted version of the diff, maybe a minimal version of the diff, and then maybe it has a raft or something else that lets you open it out into whatever object, whatever format you want, if you didn't specify a format when you specified the original diffuser. Okay. I also strongly suspect that that third argument to diff is going to wind up being something that is a bit like places where we use rules that say source destination and might be that the. I, I don't know. I'm. I'm just. I'm. I'm not sure yet.

But, but can you mention one definite place that I'm not familiar with source destination?

Okay, so they're like text translation. Text translation, Lang 1, lang 2. See that? So one translates into the, into the language lang and the other translates from lang 1 to lang 2. And what I'm imagining is something where the right hand side is kind of the format you want it to end up in. I don't think it's quite right. That's not quite right.

No, I think this is, I mean, I think your idea about it being more like import export, you know, elements is, Is better, is a closer analogy.

Yeah, but then. All right, but I think. And then for the application of a diffusion, I'm wondering if it can just be a sub value. Now, I understand you want sub values for the diff object, but maybe if you. I don't know. Again, I'm not sure. I don't. I. Right, you see what I'm saying? You just, you just take a diff object and you apply it to something that may not be right. Because.

No, because, because. Because in the case of strings, you can't disambiguate.

All right. Okay. And you have to give conflict options.

Yeah, yeah, yeah. I don't think that.

Okay, that won't work. Okay. But then I, I do wonder, UX wise, I mean, if you look at, if you, if you scroll down to some of your display forms for these things, I do feel like there could be, you know, by the time you're formatting that type of stuff, you could have something which allows you to choose to flip around format, so to speak, either with a raft or with an element in the actual, you know, displayed object itself.

Right. And I've had that in mind as an interface that could be built on top of these raw elements. But yes, that could be sort of burned into the elements themselves, I suppose.

Right.

I, I'm just, I mean, I think, you know, that's a pretty sensible, you know, default formatting there. The, you know, the table looking one with openers. But I'm, what I'm arguing is, you know, if you want to do something with that, you know, copying that into an input cell, it's going to be kind of obnoxious as opposed to just the summary box of a diff object.

I understand if you want to copy it that way as opposed to calling it percent seven or something.

Right.

I mean, you could say that about every expression we generate. Oh, it's too complicated. You're not going to want to copy it into an input cell.

Well, that's, and that's why we have summary boxes for a lot of things.

For some things. Right. But the question is we. Okay, the trade off is.

And that, that's also why we have image size multipliers.

Yes.

So when, so an image automatically drops down when you start typing around it to make it less unwieldy.

Yeah, that's also a good point. But I mean, the point is that the place where it's a summary blob is. Makes sense. Is the case where you really don't, you know, there isn't a good way to see the thing in summary form. You know, it's, it's a giant sparse array. There's nothing you could display there that will be a reasonable, faithful representation of the sparse array. Whereas here there is, there is something you can display and you might as well display it up to a degree.

Up to a degree. I mean, even.

Right.

I mean that's the equivalent of sparse array of, you know, 120006.

Yeah, fine. Well, okay then, then, then I've got another comment. If there, if it is the case that the thing is, you know, I wasn't going to say too big, too big to show type Thing. Okay, then I think we need a different format for the thing. We need something which has elision built into it so that the thing you show isn't too big to show. I mean, it's like data set. You could say it's too big to show, but we have paging in a data set.

Yeah, I mean it's. And this is common in every diffing interface. I see. You know, there are only two possibilities. One is they find some way to say if it's too large, we're not going to show it unless you really want us to, or it, you know, becomes crushed under computational load and unusable.

Right. So, okay, so fine. So then, then what we would do here is it's like a too big, for example, you know, like, like the. Like the. What do we call it?

Output size limiter.

Yes, right. It's like that kind of thing where if it's. If it's, you know, we show a certain amount of the diff, making it clear that this is just a diff frame. Right. Where you're seeing a window into the diff up to a certain size. That seems like a very sensible way to do it. And that way you can pick it up because it never gets too big and you can use it. You know what I'm saying? And that way you get best of both worlds. And also like the output size limiter, we could do exactly the same UX approach. We could have a tray at the bottom that has options for what you can do with it. Because this thing isn't an end in itself. It's a thing that you're going to use in some way. I like that idea. You know, frame it, tray it.

Right.

And one of those buttons could be convert to summary box, if that's what you want.

Exactly. Yes, yes. And then you can. And then, you know, which is analog of iconized, which we have for the. The too big thing, I think.

Yep.

Which might be the thing for this as well. It might be iconized as well here.

So operational question, we're going to meet again. Is there someone who's not here now that we should bring into the next meeting?

I don't know anybody wants to. I mean, maybe Nick, if we're going to get very algorithmic on this, I don't know if there's anybody else. Maybe somebody from Bioinformatics team. Oh, and another person we should bring in is somebody who's been involved in Docu Tools, blog tools.

Could that be Brian or somebody else?

You ask Brian. I don't know.

Okay.

So reach out to Brian. Reach out to m. Yeah.

Yes.

Okay.

This is great. You know, we're finally knocking off all these things that we've been planning to do for years. Good stuff. Yeah. This is really going to be useful.

You know, I mean, it's. It's. It's been a hard problem and, you.

Know, Yeah, I can tell a lot.

Of genius stuff going on behind the scenes here that we haven't even touched on, so.

Fair enough. I mean, we also need to talk about notebook distance. We got another solid hour, hour and a half meeting ahead of us on this, but we're, you know, we're gonna grind. This is going to get a bit more polished. It's going to be great.

Okay.

All right, Thanks a lot, guys. Okay, see ya. Bye.