Live CEOing Ep 731: Language Design in the Wolfram Language [ExprStruct, Longest+Shortest, and More]

All right. Hi everyone. Welcome to another Wolfram language design review, part of our language completeness and consistency series. And we have several slightly complicated looking topics today. All right. Expert in terminated evaluation. Yep.

So in 13 three, you know, terminated evaluation returns with one argument, which is the reason.

Yep.

We would like to have it actually return what it could. What the, the unevaluated thing that it was had got so far.

Right. And so, you know, we, so we have it sort of working. Although right now it'll only do this if you have previously, you know, used an expert struct in the session.

And why?

Well, I mean, there are several reasons, one of which is that it will add an extra half second to start to every kernel startup to, you know, since we don't want to be loading this thing if we've already hit the recursion limit.

Oh, Christ.

Well, hang on, hang on. Can I. Right, so initializing the data structure uses the evaluator. And if we hit recursion limit, we don't want to use the evaluator. So we could, we did some work to pare it down to load it at startup time, but it wasn't zero cost, it was.

Right.

So it's not going to work. So it's not going to work. We're not spending startup. Hold on, hold on.

Right. Since then I've been thinking it might be possible to load it without using the evaluator or to delay the evaluator part. And I could go and investigate that. I'd be willing to do that if that would.

That seems sensible to me. I mean, I think we can take a cost if it takes an extra half second when we are about to have a terminated evaluation. So what?

Yeah, yeah.

I mean, I presume at these points we can allocate memory.

Generally speaking, yes.

The two issues are orthogonal. So yeah.

Yes, fine. Right. I, I think it would be interesting to try to cut out the evaluator part of this, so I'd be happy.

Okay, fine. So that's what we're planning. That's what we will plan on, is, is that it will. So now, as I understand it, one feature of this kind of terminated evaluation, it's actually a very interesting case, is that we've essentially got, I mean, I hate to go physics project on it, but you know, it's kind of a space like slice of what happened. That is there could be, you know, we don't in a sense have everything evaluated, but we have a certain time slice, so to speak, if that makes sense. The reason I'm bringing That up is that two things? You know, equality testing is funky here. Right? Are they the same terminated evaluation or not? Do you understand what I'm asking?

Sure. It depends slightly on the state of the evaluator though. Does it?

No, I mean.

Let'S look at the gallery. I mean, you know, there are. It's, you know, that, that is something I wanted to discuss. And you know, I'm not sure how much we're able to affect this, but, you know, so. And would you mind boosting the magnification just a bit? I. I guess my screen is kind of small, so I'm having a bit of trouble. Thank you. Right. So, you know, I think we all, we. We all sort of can understand.

The.

First couple of examples. So in the first one we're setting. We're. We have a saw, we're solving for A and we're saying A equals solve. So we. So, you know, the solve evaluates, the set evaluates. And then it tries to, you know, evaluate the returned A. And it's like craziness. And so we understand that.

Yeah, yeah, yeah, yeah. Right. You know, I mean, in this case, I mean, your code is rather obscure here, but I mean, what's happening is that last is extracting the expert. And this is various pieces of action on the expo struct, which I don't necessarily understand.

Right.

So I do understand what that's saying. It's doing construction, but it's doing it with the defer. And that means that this thing here is going to explode on contact if I actually run it.

Yeah, if you were to copy that and evaluate it, then yes, that would explode on contact.

By the way, should there be any indication that that's an explode on contact object, you know, in its print form and so on?

No, because the whole point of defer is that it's equivalent to typing that thing in.

Okay. Okay, I see. And it won't explode. And except for the fact that the A equals. Has been evaluated.

Yes.

All right.

So the second example is basically the same thing. We can skip. That one is kind of boring. The third one is where things sort of start to get interesting because I'm not sure I totally understand either the result. Why we have both. We have two evaluated X's and one unevaluated X.

Okay, so let me comment on this. This is exactly the thing I was yakking about about space, like surfaces. Okay, shall I explain this?

Sure.

Okay, so think about the evaluation trace. And maybe we could generate a trace graph here. Could we generate a trace graph for A few steps of this I'm not sure. But anyway, think about the evaluation graph that you get from this. There's a question of how far do you go on each of those exits. Right. At some point you're going to kind of bundle. By the way, is other people hearing a crackling sound?

Nope.

Okay. Okay, I need to report that for my setup. Okay. So you understand that. That you could go a different depth. So let's say you said X equals list xxxxx, right? Each of those X's could evaluate a different distance. Am I making sense? Anybody understand what I'm talking about? Should I do an example?

No, because the less they're nested at different. Yeah, they're nested at different levels. And so obviously they'll evaluate less the nest or the more nested they are.

Yeah, right. But you can, you can do. I mean, I'm not sure how to make the best example here. You can. You think about this as a graph in space time, right? Space is the successive elements of a list, for example, or other parts of this data structure. Am I making sense with me so far? Yes. No. Maybe. Time is successive iterative evaluation of something. Right? The thing is evaluated, it's evaluated again. It's evaluated again, and so on. Right? With me so far? Yes.

Yes.

Right. So there's a front that you can make of how far you have evaluated as you go across space. Right. So you go across these elements. Each element has evaluated a certain distance and a certain number of iterations. Some elements require other elements to have already been evaluated in order for them to be evaluated. Right. Others are spaced like separated. They are at different ends of the list, for example, and their depth of evaluation is independent from the depth of evaluation of the other one. Am I making sense? Do you understand or not?

The point about if you had, you know, recursion within a recursion.

Yeah. For example. Yes. Do you guys understand this or do I. Should I try to explain this more?

More?

I mean, is this. Is this obvious or is this totally obscure what I'm talking about?

Explain a bit more, if you don't mind.

Okay, let me try. Let me try and do this. Okay, let me see if I can find some examples. Okay, hold on. I really should be able to generate this stuff. And. And Ian, we should be able to generate it from your trace graph stuff, but maybe we can generate. So.

So the issue with that is that trace graph relies on trace. So if trace, you know, hits.

Okay, I understand. We're not going to go to the recursion Limit. I'm saying that we need to. We need to just look at this. I mean, maybe we can do this with. Look. I mean. Okay, okay, hold on.

Let me just as a meta comment that trace business is the next topic, I think, or the third topic on the agenda.

Okay. All right, let's see if I can find examples here. This may not, may not show what I need. Unfortunately, it's beginning to here. This is a complicated business. Ok, so. Oh, wait a minute. Where is this stuff?

What was wrong with the tree that you just passed?

That's not what I was trying to show. What I was trying to show was. See, See, there's space, like.

Yeah, these trees.

Okay. Yes, but this is only a part of the story. Okay, so. So the problem is. Let me think about this. What do I. Why do I have a good example of this? Hold on.

I think what you want to say is that siblings are space, like ancestors, descendants are time, like.

Exactly. That's what I'm saying. Yes. Yeah, that's what I'm saying. So. So here. Gosh. Maybe this. Oh God. Okay, this is a typical time like sequence not showing down the page where a single string is being rewritten and it just rewrites, rewrites, rewrites that same string. Okay. Things get more complicated. Here. Yeah. Okay, so this is an example where the ability to do a particular operation depends on other operations having been done. Do you understand that? Do you see what I'm saying? In other words, something down here. See.

The rule only matches after some previous rule has been applied to produce that exact expression.

Exactly. So that is a dependency. That's a causal dependency. And sometimes it's just a local causal dependency. It goes go to down in a timelike way. Sometimes there is spatial entanglement. Does that make sense? Sometimes it depends on something in a different place in space. Or in our case, a different part number. People understand, no. Yes, Maybe. Yeah, maybe. Right. So the issue is, if you look at this picture, there are different orders in which you can do these updates. Okay. Each of these pictures shows a different order of doing the updates. Am I making sense?

Yeah, right.

Which update is done when that defines a foliation of the space of what you know what is being done. When is. You know, we have a sequence of slices here. There are constraints on the slices because things that are time like separated cannot happen. Things that depend on the output of one thing can't happen before that thing has been produced. Am I making sense?

Sure. But I mean, yeah, it amounts to graph traversals in various Ways.

Yeah, that's right. That's right.

It's equivalent to graphic, where leaves happen before their parents.

Well, happened before. It's a traversal order, right? This thing. Yeah, yeah.

Yeah. So. So if you change the traversal order, pre order, post order, in order, whatever, then you're going to change the way where you get the terminated evaluation. That's one of the issues I don't understand about this terminated evaluation. Because what you get is dependent on how you evaluate or traverse or whatever the algorithm is that's doing whatever it's doing. And so if we change some algorithm to work in a different way, we'll get a different set of terminated evaluations in a different order. And these terminated evaluations, I'm not sure exactly sure what the goal of them is because you get these nested expressions which contain at some level inside the expression determination, evaluation. But surely what you want is just why is it useful to have a nested expression with several terminated evaluations? Why is that useful?

I'm going to tell you several reasons. Okay, so first point is the terminate evaluation object is a frozen. You know is. Okay, so in this case here, for example, in the end we'd evaluate to this. See what I'm saying? In the event the end result is just that one thing that. Well, I don't know what it is. No, in the end, that's right. We're sorting a list here. So in the end it's the sorted list here. See what I'm saying? But yeah, this is actually a pretty good example. I mean, we could terminate this evaluation at a different stage, right? And depending on our evaluation order or our traversal order, however you want to look at it, we will get a different terminated result. Does that make sense?

Yeah.

Okay.

As long as there's no dependency, like the fact that one terminated thing doesn't influence the result of another. I mean, if there's a dependency of the two, then.

Yeah, I know, I know, I know. This is why I'm bringing up these foliations. The whole point is here, that, that you are freezing it in at a particular stage here, right? I mean, it's. This is charmingly related to quantum measurement stuff too, but let's not go there. The, the. Okay, so now the question is, what do you learn from this terminated thing? So, for example, you know, if this thing is confluent or causal invariant, then it will be the case that you could always pick it up and it doesn't matter where you froze it. If you keep going, you'll always eventually get the same answer. Am I making sense?

Okay, if that's the case. But is that, how often is that the case? Is it always the case?

I think for when you have pure functions, when you don't have side effects. I believe it is the case for our language. But it's not self evident.

But it's random anywhere in your computation, then you're screwed.

That's not a pure function, so.

Right, yeah, but I'm just saying, how reflective is that of the language as a whole?

The answer is I believe so. For example, for combinators, which is what this whole thing is about, right. There are all these different traversal orders here, right. And all of them will eventually give you the same answer. So you can actually see that. I'll show you just for fun. Where is it? Let's see here.

Right.

So Stephen, can I point to a concrete example in the notebook that.

Yep. But I just want to explain this one point. Okay. It's one thing. Okay, so this is confluence in action in combinators. Okay. These are different updates you can do. Is this making sense to people? These are different, you know, this, this represents a different evaluation front. These are different places where you can do a, an update, but in the end you'll always get the same result. Make sense to people.

Lambda calculus, isn't it?

It is, yes, yes. It's a property of combinations. Lambda calculus. And our language, when it is pure. Right, right. And it should be the case. And by the way, I mean. Okay, so in our language, just so we're clear how it usually works. Well here these are examples. But let's see if we've got a bigger example. Okay, that's a nice big example, okay. Of many different paths of valuation. Now the thing to understand is our language always picks one evaluation path. People understand that. In other words, when we do our pattern matching, et cetera, et cetera, et cetera, we're always picking a single path. Makes sense.

Heads go first, left to right.

Yeah, exactly.

Blah blah, blah.

Exactly. So this is like this here is basically says. I forget what this is. Depth first evaluation. Okay. So this, this one here. Leftmost, outermost evaluation, which is. No, we're doing leftmost innermost. I think by default this is leftmost outermost. That's that that path is leftmost outermost. This path is depth first. Make sense? So I mean the thing that we are looking at in the future is being able to generate these whole multi way graphs of all possible orderings. But right now, but, but so when we freeze, we are presumably Freezing somehow in some rather, you know, we don't really know quite how it works. We're freezing across something which is fundamentally being done with our usual evaluation order. But we didn't finish our evaluation, so it might matter. Okay, all right, now it's. All right. Point me to an example.

So where it says these don't look so great near the bottom of. Right. So here we're mapping minimize across a table of some initial values or really functions to minimize. And we two of those things become terminated evaluations, and two of them evaluate fully. And when you look at the expressions inside of those terminated evaluations, I mean, I guess the problem, perhaps the issue here is that it's really a, you know. Well, it's recursing more than we expected. Not that it's a true infinite recursion, but when you get the, you know, look at those two terminated evaluations, you get these very innocuous looking expressions popping out.

Yep. So what?

Okay, well, you know, on some level it's, you know, that recursive to your.

Surprise, there's a free queue there because where the heck's the free queue in any of this? Right, right. That free Q is something from some internal code.

Yep.

I mean, itai Couldn't you just set recursion limit higher if you realized that this was.

Yes, you can. Okay, and, and that example is like just below the, the, the, the screen on the notebook.

I see.

The, the thing I find very hard to understand is if we wrap that map in quiet to suppress that, that message, we no longer get a list. We get a single terminated evaluation. And I'm not sure why that is. I, maybe none of us understand why.

That is, but it, it's because the terminated evaluation gets wrapped at level zero of the evaluator sequence. Whatever it happens to be doing. It's difficult to, to redesign around that.

Okay, can, can you explain that a bit more or, or, or make that more specific to this particular. These two.

Well, so you have a list of operations or of whatevers of evaluations and the evaluator before it evaluates, list of all that it evaluates.

Oh, right. So in one case I've constructed the list. Well, but no, in one case I have map. Oh, but your, your, your point, your point is that in one case I first have a list and then MAP creates a list with the function applied but not evaluated and then that list evaluates. Whereas in the case of quiet, the, you know, it's now one level deeper.

Right? That's correct. And, and it, because it, you Know, doesn't wrap that terminated evaluation until level zero. That's why you're getting that.

Okay, and so guys, look, there's several things here. First of all, there's the level of canonicalness of the cutoff in the terminated evaluation. That's one thing. The second thing is when we cut off, we could be in the middle of a piece of internal code.

I'm sorry, what do you mean by level? Do you mean.

Okay, so look at what's happening here. Look at what's happening here. Okay, yeah. This is iterative evaluation. This is re. Re transforming an expression many times. Right? So I mean level in that sense. I mean time like level, so to speak. I don't mean the levels in our trees. So I'm saying, I'm, I'm saying maybe I should call it iteration.

Then you can confuse it with iteration limit, which.

Is actually very related.

Well, yeah, I mean it's. It should have been named something like evaluation limit because it's not iteration per se.

Okay, look, look, it is an iteration if it is not a multi way system. If it's just ding, ding, ding, ding ding down here. It is sort of. I mean, it depends on what's happening in the, in the evaluations. But, but.

I'm really referring to our internal use of iteration limit. Different subject, really.

Yeah, I understand, I understand. But the point, what makes this thing branch like this is that there is space like extent to these expressions that allows there to be more than one place where an update can happen. If these expressions were all sort of not space like extended, there'd be only one place you could update and it would just be a time like sequence. Am I making sense?

If rather than, for example, if rather than expressions you just had numbers and functions between numbers?

Yes, right. Or if you have a single X that's just going X x x x X x X. You know, if you said X equals X, if that was allowed to wrap, to run around. If say A equals B, B equals A. I think you'll get a pure line here. You see what I'm saying? Do you understand what I'm saying? A equals B, B equals A, et cetera, et cetera, et cetera. Just go ababa B ab and there's no spatial extent, there's no choice. Right? So as soon as there's a choice, it is not unique what the next state will be unless you add in our evaluation strategy. Right? Given our evaluation strategy, we'll pick a particular place to evaluate next. Am I making sense? That's a particular path through here. But the fact that there are multiple things that can happen at a given level here is a reflection of the fact that there is a space like extent in the case of this. I mean, you could also have. Okay, there's also this notion of branch like, which is that you've got. Even in the ab, if you've got A equals B and you've also got A equals C, you have both of those transformations possible, then you can have a branch like separation. That is a choice just because there are two possibilities rather than. It's a choice because you have to determine in space which thing you update.

I see. You don't need space like separation to have branch like separation.

Exactly. Exactly. Okay, so I mean, okay, the bottom line here, this is a very complicated subject. What are we trying to actually do here? So I hadn't really internalized the fact that we will be capturing potentially chopped off internal evaluations with this expert.

Yep.

Okay. And the notion of canonicalization with the expert struct. Okay. If we want to have a restartable evaluation, This is possibly useful for that True statement or not a true statement. If you want to say we went a certain distance now go another hundred steps. That is something we should be able to.

I wonder if that's true because like you change the sorting algorithm or something, you change the fact that something caches some of its results the first time it goes through it. It's not reproducible in any way. You're assuming it takes the same time to evaluate time and space every single time you evaluate something. But that's not the case, is it?

That's. Why does it. It's only that. That the intermediate state is. Right.

So I would say that in some cases it's potentially re. Restartable. Like, you know, like the, the. The example we skipped over with those square roots there. There's a typo in the initial condition which is causing this thing to infinitely recurse. Rather than, you know, get to the base case and. And evaluate and you know, so there. Okay, we have a snapshot and we could, you know, sort of go from there. But like in this minimize example, right, if you copy that free queue out and evaluate it, right, That'll just evaluate to false, which is obviously something you could never get out of minimize because. So we've sort of captured a little subtree, but not the whole.

Why didn't we capture the whole tree? I don't understand why it didn't capture the whole tree at that stage. In other words. In other words, take this picture. Okay, We've got multiple pieces that are evaluating here. I don't understand why we're not capturing the whole evaluation front.

Danny, is that something you can shed any light on?

I realize I'm not understanding the question fully.

Well, here's the point.

It mean capturing the expression at the point it was caught, not the point it was thrown.

No, no, hold on.

You captured at the point it was caught. Oh, I'm sorry. The terminated evaluation gets wrapped at the point it was thrown. You're correct.

Yeah, that's what I mean, but. And that's why you get free Q, you know, which is exactly because it.

Doesn'T have the whole of the dressing. It doesn't have the framework around that thing. It only has a thing that. Correct.

It doesn't have all of the internal C curve internal code that we have. You see, there's like code inside of a pure top level code. It could do what you wanted, Steven, or closer to what you want for code that's got, you know, sort of.

How can there be a layer of C code in between these? I don't understand that.

Because minimize is implemented in C code.

And the counter for evaluation. Wait a second, so let me understand. The counter for evaluation levels is the number of levels outside. Then it hits internal code, it doesn't count those levels. And then from the internal code it calls the evaluator again and then it starts its counter again. Is that correct?

Doesn't restart the counter. It's only in rare cases it restarts the counter.

No, no, I understand. It doesn't restart the counter. It continues the counter. So, correct.

There are a few places where it does restart the counter, but not, Not. What are they? Oh, like parsing something or something where you really want it to work. Like loading a packet.

Message printing.

Yeah, yeah.

Formatting, you know, interacting with the front end.

Right, so. So the problem. I understand the problem is you have. I mean, in the combinator case, I hate to be. Maybe that's a very obscure case. You kind of drill down some SSS thing, but around it there is context. So, for example, if we look at a combinator evaluation. Okay, so let's take here. This is a piece of combinator being evaluated, piece being updated. But around this thing. That thing. Oh, no, actually, it's not what that is. Or is it somewhere here I have some examples of. I mean, I have to say, by the time we're using combinators to clarify things, there is an argument that we have fell. Fell. Fallen deep into obscurity. But okay, here's what I'm looking at.

Okay.

Okay. So here the colored pieces are the pieces that are being rewritten. Okay. But it isn't obvious. But the. The issue is that one of these might drill. One of these might have evaluate, evaluate, evaluate. And that goes crazy. But it doesn't. As we return it, we are not also including this piece here. Right. Make sense to people.

Mm.

Right. So, I mean, that's. Yeah, I understand that point and go ahead.

A couple of points which you might disagree with. The way we currently do. The termination at the throwing point I think is very useful, particularly with this data structure in place, because it lets whoever wrote the code know what it was the evaluator was having trouble with. Often it is an expression like x equals x plus one. Very, very often in a more subtle way, this is uncovered. I can't tell you how many problems in our own code. It's measured in the hundreds, low hundreds, but still. So I think that's important. And if you surround it with too much by doing it at the catch end, then you're just, like, more likely to hide the actual source of the problem. The other thing is, for Itai's example, where we really should have been able to do it, but the recursion limit just happened to be set a bit too low. I don't think that's a very common case that we're going to encounter. I haven't seen a lot of it. I haven't seen bug reports about it. Yes, it can happen, but it's a bit artificial. And once you know what the problem is, and you can usually deduce that by looking at the result inside the terminated evaluation, you know, okay, I'll set recursion limit higher. So I think we want to change what we're doing.

Guys, guys, look, look, look, look. First question was, is what's inside the terminated evaluation a full expression that could be restarted? The answer is no, right now. Do we know that it's no? In other words, can we tag that? Because in some cases it's yes. In X equals x plus one, the answer is yes, it is a restartable thing.

Wouldn't it need to care?

Okay, so that's a question. Let's pin that question. Okay. Could we know that it's not restartable? The answer is we could know because it went through internal code.

Down code. We could know that.

Yeah, but I mean, given the caveats Mark raised already, do we. You know, it's. It's. It could take a whole different code path the next time.

Sure, sure, we understand all of this. We just want to know the answer to the question. Is the thing inside the terminated evaluation a complete representation? Okay. When we call it terminated evaluation, it suggests that we have a whole evaluation and we froze it. Okay, yes, but in fact, that's not what's always happening. Sometimes it went through. Which I hadn't really understood. It went through something that is unfreezable by us here. Okay. And what we got left with was just a fragment after we went through those layers. Right. And we could know from the stack trace, presumably, which of those we're on. I mean, are we returning the stack trace at all here? No, no, because that will be useful, wouldn't it? I mean, that. That would tell us. That would tell us the path which led us to this. Okay, because it would be great, except.

It would be huge.

Yeah.

I was gonna say. Now you can get into the situation where memory is a problem.

Yeah. Okay.

These internal. These internal states or these, These intermediary states, they can be exponentially larger than the final result. And how useful is that to wade through or even to handle?

You know, I tell you, it all happens in combinators that. That exact phenomenon happens regularly in. In these things that. That it gets big. What's that?

I don't think it's what we want to do.

No, no, I understand. I understand. So. So in this case. So look, a good exercise if we want to understand this is, you know, and. And again, it's a very bad sign when combinations are the way to make it more transparent. But we could think about what would you do with combinators? How could you return the partial evaluation trace? So with combinators, what you would do is you would return. Yeah, you would return the combinator expression, which you can always do in this case. And the reason. But we can't do that because we are going through something which is not representable symbolically by us. Right.

The combinator evaluator could quite easily have its state representable. That's. That's what you want. That's what you're trying to capture, as well as the bit that went wrong.

There is no. There is no independent combinator evaluator. The state of the combinator evaluation is the combinator. Right. Whereas, as Mark is pointing out, there is additional state to our evaluator, which makes it not pure in that sense.

But, but aren't you applying rules of, you know, rewrite rules of. Of the lambda?

Yeah.

You know, so those, Those themselves have a. You know, there's. There's some sort of context to It.

No, they're stateless. They're stateless. One of them is red, one of them is blue here.

But there's a picture there. There's. There's a picture.

What do you mean? I mean, that's.

Of the whole.

There's a snapshot.

Okay. Okay. You're saying that you might need to know the stack trace is. Where did you apply the red? Which, you know, where in the expression, did you apply the red thing, for example?

Yeah, maybe that's. I don't know.

Yeah, no, that's right. You're right. There is that issue. Yes, there is that issue. So in other words, the current state, okay. Because of confluence, it doesn't matter what the history was.

Yeah, you don't really care what the history is.

But. But because of confluence, which we don't have, when the. When things are not pure and when there's a random. Or when there's some kind of caching or some such other thing. See what I'm saying? Right? I mean, we. If. If the thing was pure, like combinators, then the history never matters to the future.

Unless you want to freeze in the middle and have a little look at it. Where you are.

Doesn't matter. Doesn't matter. If you freeze here, you freeze at that stage, right? You can always go on, and it doesn't matter.

I know you can always go on, but you might want to make a picture of it. To make that picture, you need some knowledge.

No, to make this whole picture, which includes the history, you need a knowledge of the history. Yes. See what I'm saying? To get the current state, you do not need that. So, look, I think what we've got here is. We've got. Okay. What we more have is essentially a hash code for the thing that. On which it got blocked. We do not have something which is a restartable full expression in terminated evaluation.

Correct?

Right. So now the question is, how good is our hash code? Right? In other words, to what extent is it true that if it. If we ran the same computation twice, we would get the same hash code? And to what extent is it true that if the hash codes are the same, it really is the same? Am I making sense?

The same means terminated at the same point?

No, it means that were we to be able to continue this computation. Okay, let me give it the following example. You've got a list of things, okay? And they all, you know, burn out with terminated evaluation. Okay, let's do a specific example, because this is. I mean, it's really. Okay, so let's Say we say, let's say, you know, J equals J plus one. Yeah. Okay. Oh, God. Okay, so it says. I don't know why. Okay, let's try this. Okay. Why did that not give a data structure? Why did it not.

You're you.

You need to, to evaluate, initialize. Yeah. You need to do like create data structure. At the top, there's that second input will initialize things for you.

Okay. All right. Okay, so now let's go down here. Okay. Now the question is whether in that last thing, if I say same queue, What do I do? Sorry, same queue at. At percent 8. Interesting. So it's not obvious that that has to be true.

Right?

Right.

I mean the fact that that's true is because you picked, I hate to be physicsy, a cosmological rest frame. You picked something where essentially time has run the same amount every place in space. Do you see what I'm saying?

I think a shorter, easier way to say it is it's because they all choked on the same expression.

No, they all will run, run to the same choke point. In other words, it could be the case that you have. Have juice that you're using up. And that juice is, you know, after that first one. It depends on the way the list evaluator works.

You could have had two plus terminated comma three plus or whatever, or two plus two or, you know.

Yeah, this could have been a different squared. But this, this. Presumably Those things are J+J plus J plus J plus J a bunch of times. Right. Why does it say length two here?

I bet they're J plus one.

Yeah, each one is J plus one, I would expect.

Yeah.

Why?

Because that's what you assigned to J.

But it detected the loop that quickly. Why doesn't it generate a. You know.

It has to do with where it bubbles back to with the catch.

I mean, if you want to do the. If you want to do this quickly, copy out one of those data structures and look at the evaluation sub value of it and it'll show you the expression. It is visualization.

This should be visualization.

Yep.

Okay.

Yeah. So I don't know why it does that weird line breaking. That's why I don't use this sub value very often. But you can see it's 1 plus J.

Shouldn't we have a sub value for the expertstruct data structure, which is just the nominal pretty print of the thing?

Yeah, we should do. Yeah.

Why don't we just call it unevaluated?

What would you call it?

Unevaluated. Unevaluated. Unevaluated form or unevaluated expression.

But what would it be?

Hold of the expression.

Why not?

Hold complete. Yeah, hold like hold form.

Fine, fine.

Okay. Or held expression would be our usual way of saying it. Yes, held expression of that.

Fine, okay, sounds good. I'll add it.

All right, okay, so let's come back to this issue. All right, so you guys understand my point. The fact that these are equal is not self evident. It depends on many things about the way the evaluator works.

You could put a random J equals j plus random integer that might have different.

Sure, but you're not understanding my point. My point is the fact that these all went the same distance is not obvious.

Yes, yes, that's true.

Right. And the concept of equality in some sense, I mean, this is a very interesting question, right, because let me give an example with my friend the combinator again, okay? There are plenty of combinator expressions which are. Which, which do not terminate. Okay, These ones here terminate, right? But we can also look at a combinator expression, I don't know where I have an example of one, a combinator expression that doesn't terminate. So I think this one here has, has branches that don't terminate. Okay? So if they don't terminate, are they equal? Are two non terminating expressions. When is it the case that two non terminating expressions are equal? Does equality mean there exists an evaluation stage at which they are syntactically equal? What does it mean? Do you get what I'm saying?

Could mean they have the same set of possible futures.

Yes. Or it could mean there exists a future. There exists a state where they happen to be equal, which in this particular case would be equivalent. But. But it isn't, you know, and this quickly segues into transfinite numbers and all kinds of issues with those. In fact, I suspect that there is, that there are equivalence theorems that you can get that go up to, you know, in the transfinite number case, go up to Epsilon 0. So what, what does that mean for us? The. Maybe somebody can figure this out immediately. If you have a list X equals the list X, X equals the list X comma X. You can think of those as defining, you know, when you ask, how do you represent those things? See, if you say x equals x plus 1, the value of X in some sense is the transfinite number omega. Does that make any sense to anybody?

Yeah, X comma x. Presumably the next omega or whatever we call that cardinality of the reals.

No, it's not the cardinality of the reals. It's still it's still a.

It's below numbers. Yeah. You don't get to that until omega. To the omega, right?

No, you need to go even further than that. You can't. You don't get to that in any omega. I mean, what you get. I believe. Well, I'm. The tree is some. Anyway, you get some other omega. The. I'm not sure that the. Actually the value would be the leaf count. I think of X equals list xx. Right. The value of that leaf count is essentially an exponential.

That's not cardinality of the reals 2 to the LF0.

No, because it's not LF0, it's an ordinal number that you're getting here because what's happening is you're in X equals X plus 1. You're generating ordinals. You're going, you know, 1, 2, 3, 4, 5.

You're counting up in X equals X comma X list. You effectively encapsulate all possible Boolean decimals.

Yeah, you might be right. You might be right. You might be right. That the thing I'm. I'm asking for, which is their leaf count is a cardinal. I'm not certain. Anyway, the. My guess is that there will be equivalence theorems that you can get. For example, among the ordinals there are, you know, cancel normal form, works up to Epsilon 0 and then blows itself up. And my guess is the same is true here, that there is no. There's no guaranteed way to know. You can't prove equivalence of these things even for very simple cases, aren't you.

Even if you'd need to know the entire state, and if the entire state that led up to that is the same, then it's taken the same path. Every single thing, every single evaluation is identical. And so you'd need that. Not the future, but the past.

No, Mark, Mark, that's not right. That's not right. In the case of these pure evaluations, right. Where there are no side effects, I believe you only need the current state that uniquely determines the future.

Independent of what path it took to get there. Really?

Yes. That's the whole point. That's the whole point. Look at these pictures. Look, look, look, look, look, look.

Right. If you're not allowed to have any assignments, then the current state is really everything. Right?

Right. In this case, every one of these different rewrites here is a different possible thing that you might have done. It's a different evaluation. You know, it's a different choice of evaluation. So you could think about that. In our case, we happen to evaluate lists sequentially, but we might not. We might evaluate them in a random order, okay? And every different arrow here is a different choice of what elements of the list to evaluate next.

But what if your terminated evaluation was one of those four?

The whole point is, for any one of those four, you keep going. And when you. And. And you end up always at the same place. That's what this confluence property means, okay? And that's what. Lambda calculus has that property. Pure lambda calculus, combinators, our pure language, has that property. Now, every time, as you correctly observe, every time you get something from the randomness pool or a different cache from the outside, you're toast, right? And then, no, you no longer have an assignment. Yes, if you have a different assignment, you're also toast. You're getting. It's something outside the purity of the system.

It's a side effect.

It's.

Yeah, right. So, okay, So, I mean, I think what we're learning here is it is at best a hash code, right? And it is a hash code that doesn't even. It's a hash code that is both a hash code for the expression that was being generated and for the essentially evaluation history that got you there, right? Because these happen to be equal in this case, but we can't be sure of that. So two things which in truth are equal, that is, let's say they terminate after a million steps. Okay, so let me show you an example here. But there are combinator expressions. Crazy, crazy combinator expressions that. Yeah, look, these ones. Yes, yes, yes, Here we go. Yes. This is actually a good example. Okay, so this is a combination expression. This is the size of the combination expression as a function of number of evaluation steps. With some evaluation strategies it terminates and some it does not. Okay? When it terminates, it's always the same, but it might not terminate. And so there's no way, you know, if we get one of these non terminated 7,000 element expressions, right? And that's our termination here. Is it equal to this thing that used a different evaluation strategy that terminated here? If we took that expression with 7,000 elements and we used a better evaluation strategy going forward, it would terminate in the size. Whatever it is, size 8 thing. Does that make sense? But there is no way on earth we're going to be able to figure out that this terminated eight element thing is in any way equal to this growing without bound one or this other one growing in a different way without bound. That makes sense. Yeah. Boy. I mean, it's. I. I will have to say, you.

Know, I I, maybe with some theorems, in some cases you might be able to, to make.

Right, right. I mean, look, I, I'm, I'm sorry, I, I, I seem impatient here, but I have a tremendous advantage because I've been thinking about these terminating writing things for ages and you know, this stuff is pretty complicated. But I think, you know, the, unfortunately the second argument of terminate evaluation is not as useful as I thought it was going to be.

I think I disagree with that. From a practical point of view, it's very good for debugging.

Okay, but is it because it's like using trace rather than using a debugger and that's why I never use it because it just grows too enormous.

But this expression doesn't grow enormous. That's the nice thing, thing about it.

Well, I mean, I think the, the fact that the, we have, the fact that we encountered a terminated evaluation has been very useful in uncovering bugs and fixing them.

I'm not arguing with that.

Yeah, but, but Mark, right now the way we did debug these is usually they come to me and I set a breakpoint in the two deep function and when I get there, I, you know, hit look at the stack trace and find out where the function has been, you know, where the evaluation has spent its time. Because you're debugging it in a data struggle. Huh?

Because you're debugging it in a debugger. That's why it's useful.

Of course, but having this data would save me that.

Like the free Q, what was the free queue? What did that tell us?

That's an anomalous case where we just didn't have recursion limit set far enough. So it stopped, it got cut off in a case where it would have finished.

Okay, can I make, I think that.

Should be an example in the documentation. I think that's a great example because.

I was going to make a suggestion about this before you added the data structure with the second argument and that is that why don't we have terminated evaluation work like indeterminate, where it has upcode and these things subsume each other and you just get the top level thing is just a terminated evaluation because.

Then you can't really use it to debug. It's like, it's like a referee of a paper saying there's an error in, in your theorem. You know, it's like it doesn't tell you what to look for. From a theoretical point of view, what you say makes sense, but it's a.

Compact representation of the fact that you're evaluation failed rather than being something that grows with the size of the expression. Well, I mean, what I don't understand is this two plus terminated evaluation comma. And you get this bunch of these terminated evaluations that grow with the size of these.

Well, do they? How big do they grow? Is there a problem?

Well, the terminated evaluations themselves don't grow. Right, but they may.

No, but the size of the expression that contains them, you might have many.

Okay, that's a different thing. We're not worrying about that for right now. We're just saying these are the leaves. This thing, it's a hydra. It's. No, it's a recursive hydra that's generating heads upon heads and so on.

Yeah.

And what you're doing is you're cutting off, you know, at some level, you chop the thing off and the tree no longer grows. And you're saying the tree might already be quite big even before you allow. Even before you chop off its heads.

Yeah.

Okay, let's not worry about that for a second.

Okay.

Because if I can, if I may contribute. Right. Originally we had the design where we didn't have terminated evaluation. It was just a system exception that you had to manually catch if you wanted. And Steven complained that, you know, that way you have.

Right.

If part of your calculations exceeded like in the pure map case, then you know, you've lost that result. So this way we're sort of right.

This is the correct way to do it. This is the right way to do it. This is the thing where as you drill in sort of a time like direction, certain places in space, you know, have they run away. Okay. In certain places in space, you know, sort of time is running too quickly, it runs away and you chop it off. And other places it doesn't. But. So I've got a proposal here. Okay, here's my proposal. First point is that the print form of this be, whatever that held expression thing is. Okay. Be a short of that held expression. Okay. Point one, that we change the print form of terminate evaluation so that that thing is the short of the held expression. With one exception. If it went through internal code before it got here and we can detect that, assume we can detect that, then I claim we should display it differently. In other words, if this was a genuine, you know, sort of front of the evaluation, we display it by showing where it got to in some ghosted out fashion. If it was not the front, if it was only part of the front, we display it differently. Like we display it what's that.

Can we determine that? I'm asking the usual suspects.

Yes, can we determine that, Tom? Can we determine that?

I mean, we could, we could know if it passed through down code.

That's what I'm asking. That's what we're asking.

I think that's. But that might, we'd have to think it might always be. Might not be useful.

What do you think? Okay, if. If it's like trivially always passed through down code, it's not going to be useful?

Well, that, that's. Yeah. I mean, it needs some investigation.

Okay, fine. Let's assume you can do that. Let's assume that the N minimized case can be detected. Okay. That because anytime that it's not going through down code, you will have sort of the complete expression as it is contained in that express structure.

Well, J equals J plus 1 is going through the down code for set.

Well, and you do. Right.

And.

Right.

The set disappears. Right. The. The set evaluates successfully and then it's just the, the.

So I, I think that's. Yeah, right. It's when. When. Okay. Does the thing get left as context or not? Is the question. And so let's assume we can determine that. Okay. Then my proposal would be that we have a nice print form for terminate evaluation that is essentially a ghosted out expression that looks like it. You know, we have to. Some icon. Icon. Iconic version of this thing was sort of halted in its tracks and could go further for the other case where it's just a sub piece. We have something where there's sort of a big ocean that is around it and we just see that in sort of a peephole, so to speak. Did you. Do you get what I'm saying?

I get. I'm not sure I like it, but.

Well, that's my proposal. So I mean that, that essentially what we're doing here is we're generating a print form which is useful to look at. You could, if you wanted to actually extract the expression from it. But you know, on the grounds that this is useful for debugging but not particularly useful for further computation. You see what I'm saying?

I'm really not convinced that this distinction is easy to make in the code.

Okay. Okay. I don't know. I don't know. So let's determine that that's a separate issue. We can come back to that another time. If we cannot make that distinction, then we have a further problem. But let's find out if we can make that distinction first. Even if we can't, then we, we have something which is primarily a print form because the first thing I'm going to want to know is what is that data structure? What's in there? Do you see what I'm saying? So why not just show me?

Yeah, that's fair point.

Right? So I mean show me a short of it and that'll be, you know, that's, that's, that's the right thing. All right. A fascinating topic, but I think we, we need to. Unless this is trivial, I think we need.

Yeah, I think we should skip this.

The third one might be faster. I think that's just a straight up.

I need to go and it's not important. That's the least time sensitive one, so.

Okay. All right. Okay, I. I think we've got a possible plan here. Let's determine whether it's realistic. Right? Okay.

Okay.

Okay. See you later. Okay, thanks. Okay, bye everyone.

Bye.

Bye.