What do you think caused Tanaka to unravel a little bit in that fifth inning? Just you know, I Just thought he made some mistakes with slider tonight In the home run to Gritchick and then and then take Alvis there. You know couldn't put him away there Thought the split was better and then they but they strung some at bats obviously against them there in the fifth to get to him a little bit but Overall, I just you know some mistakes with the slider really cost them and then we weren't able to score enough He's been generally solid for you guys despite a lot of the season not necessarily having his best stuff Is it confusing to you that he's not kind of been able to to put it all together like he typically has in the past? consecutively No, because Because I think like you said he's pitch really well overall, you know, I mean The RAs really good He's pitched deep in a lot of games You know and I thought an encouraging sign. I thought he threw a lot of good splits tonight, but um, you know You know again the home run ball hurt him on a couple hanging sliders that that was kind of the difference tonight Frasier the Sunday night the pre-game stuff reset some things that just him come out and do a big home run like that Does that show you something about him? Yeah, it was good to see You know him come out swing the bat well obviously give us a lead there and then another good at bat Later in the game where you know, we had created a good opportunity to score with our first two guys on just weren't able to get anything going So it was good to see him You know with with I know that all that's been out there the last couple days to To have a focus and to go up there and really focus on having good at bats which he did Yeah, yeah, I mean that's it's it's one of those You know, obviously ball in front of you got to see it through But it's one of those you if you don't get a good read then you can't score on the base hit so it's a little bit of a tricky one obviously not the right read there and And the fact that and then they were able to get them and did a really good job of turning them into a double play so Yeah, I'm a stake there, but It's one of those ones it as a base runner can be a little great because you want to you want to do all You can to score on a if a ball is going to be in the hole You just got to be hyper aware of exactly where the fielders are and and do your best to instinctively read the ball off the bat Looked really close. Is there any consideration to challenging that play right there in that situation? Yeah You know, we waited till the end on it. So that told me it was probably pretty close, but you know, I haven't I haven't got with whether yet on exactly you know But anytime we take it down the full allotment of time, you know, I know he's looking at it pretty closely


In Massachusetts right now those crisis pregnancy centers that are there to fool people who are looking for pregnancy termination help outnumber true abortion clinics by three to one. We need to shut them down here in Massachusetts and we need to shut them down all around the country. You should not be able to torture a pregnant person like that.


Hi everyone, welcome to the Contour Ingress Controller Session. So let's do a round of intros first. We're trying to get pretty much all the maintainers for the project here. So I'm Alex Xu. I'm a product manager at VMware in the Modern Applications Business Unit. I'm the product manager for Contour. Over you, Nick. Hi everyone. My name is Nick Young. I'm the tech lead on Contour. I'm a staff engineer at VMware. Over to you, Steve Sloka. Thanks, Nick. Yeah, hey, I'm Steve. I work for VMware. I've been working on Contour since almost this inception. So let's see y'all. Pass it off to Daniel. Hi, Daniel Hansen, principal software engineer with Red Hat. And I'm excited to talk more about what we're doing with Contour. Steve Christ. Hey everyone, I'm Steve Christ. I'm an engineer at VMware and I'm a maintainer on Project Contour. I'll hand it over to Sanjay. Hi everyone, I'm Sanjay Bhatia, engineer at VMware as well and working on the Contour team. Thanks, everyone. Yeah, so let me just kick it off here with what is Contour and what we're all about. So Contour is the ingress controller for your Kubernetes cluster, which means it's a piece of software that you have to install into your Kubernetes environment in order to leverage Ingress. Ingress is a Kubernetes concept. It's one of the preferred ways to bring external traffic into your Kubernetes environment. You might have heard of service type node port or load balancer in Ingress. It's just one of the options. So we are built around another really popular open source project called Envoy. So Contour is the control plane for Envoy, which is acting as a data plane and the Envoy instance, which is deployed by and configured and managed by Contour is essentially functioning as a reverse proxy and a layer seven load balancer. And the communication back and forth between Contour and Envoy are all protected by mutual TLS. So there are a lot of Ingress controllers on the market today. And the purpose of this session is to just highlight why you might want to use Contour, given some of the things that we're working on, given our roadmap or extremely prolific roadmap and some of the fall leadership around Ingress that we are involved in. So there's something here that you don't quite understand or you have needs around Ingress. If you're not being captured in Contour today, please reach out to us in GitHub and Slack through email. We're always wanting to hear more. So if I may, I just want to highlight some of the most compelling features in Contour today. So we support dynamic configuration updates. This is driven largely by how Contour functions as a control plane for Envoy. We have very strong focus on multi-team Ingress delegation or multi-tenant Ingress. And what this means is that basically the behavior of how traffic lands into different applications in your cluster or different sub-domains, all of the domain can all be customized by different personas. So your Kubernetes cluster admin can set some basic rules on how traffic arrives at your cluster. And then each team can further customize the behavior of that request once it lands in your part of the application. Contour is very lightweight. We leverage pretty much just pure Kubernetes objects.  There's no additional software or licensing here. There's no proprietary or paid version of Contour with more functionalities. Of course, we can do TLS termination and pass through. There's HTTP to HTTPS redirection. There's also session affinity. There's all kinds of low balancing options available to you. And you can also modify request headers as well. Next slide, please. So you've probably seen the slide before in previous Kubicons, but we are already on version 1.14. We release monthly. So you can always expect a pretty stable build, very fluid release management and lots of contributors. And in the last couple of releases, we've really been focusing on a couple of things. External auth. So your incoming requests can be secured against an auth server. We've added local as well as global rate limiting. We've also added support for ingress class resource, which was released as part of the Kubernetes 1.18. And we are adding support for gateway API, which is a new Kubernetes networking sake project that is attempting to rearchitect not just ingress, but a very large broad set of requirements around dynamically sourcing networking infrastructure. So you can think of ingress classes, ingress v1 and ingress and gateway APIs, ingress v2 and Contour has coverage for both. So to stick around to learn about how we're actually supporting gateway API. And with that, I'll hand it off to Steve Stoker now. Thanks, Alex. Alex touched on a little bit beginning some architecture overview components of how contours put together. This slide here will help you dig in a little further into what that looks like with some congrats. So again, Contour is typically deployed as an edge proxy. So the goal is to route traffic from outside of your cluster into your cluster. Here you can see we have traffic from the internet hitting some sort of load balancer. Net load balancer then targets a set of envoys. So depending on your environment, you can deploy one or more envoys in your fleet, again, to route traffic. So Envoy is our data path component. Its job is to actually route traffic from point A to point B within your cluster. Contour's job is to be the control plane server. So Contour implements an XDS server. An XDS is an Envoy type protocol. What lets us configure Envoy dynamically. And Contour and Envoy talk over a GRPC connection. That's a rich data connection. So we can pass updates quickly and easily. So Contour's job is to watch the cluster for resources. So to look for things like services for endpoints, secrets, ingress objects, all kinds of different things within your cluster. When any of those things change, Contour will rebuild a configuration. It will pass those changes down to Envoy. When the next request comes in, Envoy will be able to process that request and route traffic into your cluster however you see fit. Again, so typically this is an edge proxy. This can also be done for internal routing as well. So here you wouldn't have this external traffic. You would just have internal traffic routing as well. But again, the generic example is how this works with Envoy and Contour working together to help route your traffic. So I'll pass it off to Sanjay next to talk about the next thing. So as Alex mentioned, I alluded to a little while ago, we've got some new features that we've been working on in Contour. Those include rate limiting support, so ability to set per Envoy request rate limit as well as a version of a rate limit service for you to be able to more granularly control your rate limiting requests to your applications across a full deployment. We're starting work on getting initial alpha support on Gateway APIs, a new API that the SIG network group is working on in Kubernetes. We're trying to round out the Ingress V1 support, so supporting all of the various features in terms of filtering ingresses using ingress classes, various types of path matching, and other features of Ingress V1. And also we're working on a project that we have called a Contour operator, which is an operator for Contour that is currently in the alpha state. Yeah, so let's talk more about Gateway API. So Gateway API is an open source project that was established around 2019, actually from KubeCon San Diego 2019, and is managed by SIG network. It defines a collection of resources to model service networking in Kubernetes. So what are some of those resources to cover them real quickly? You've got a Gateway class, which is a cluster-scoped resource that defines infrastructure. There's a Gateway resource that defines an instance of the infrastructure. The infrastructure being a load balancer or a proxy in the case of Contour, and of course that proxy being convoy proxy. And going back very quickly with the Gateway class really represents an abstraction of the details of the infrastructure. And so as you see here in this diagram, the different resources map to different roles. And the role orientation of Gateway API is one of the benefits of the API. If we look at existing resources prior to Gateway API, like the Ingress resource, there is no concept of having different roles to express how an application and the infrastructure is modeled for service networking. And so one of the last pieces of the resources represented by Gateway API are routes. The most common is the HTTP route, as you see in this diagram. And the HTTP route represents how an application developer would model advanced routing. For example, sending a certain percentage of traffic to one service over the other. And that's just a quick summary of the different resources that make up Gateway API. We first introduced Gateway API support in 113. It was introduced as Alpha. It's still an Alpha, so still very new. Still have a long road ahead to go with this, but this at least gives users an opportunity to kind of keep the tires with Gateway API, provide feedback not only to us, but also the Gateway API community. And we're looking forward to get that feedback and excited to have Gateway API as part of Contour. All right, thanks, Daniel. And now I'm gonna talk a little bit about Contour support for Rate Limiting, which is a series of features really that we've added progressively over the last few Contour releases. And so Rate Limiting fundamentally is about defining policies for how much traffic is allowed to reach your back-end services in a given period of time. And there are a number of different reasons why you might want to have control over this and have enforcement of this. So a few examples are for protection against denial of service attacks from malicious actors where other folks are trying to overwhelm your back-end services with extraneous requests. It might be useful for enforcing usage quotas for different categories of users for your services. It can also be useful for protecting against bugs in client applications that create unintended traffic. So lots of different reasons why it's useful, and it's definitely a really valuable tool to have in your toolbox. And so we're happy to have support for it in Contour now. And so Envoy and by extension, Contour support kind of two main modes of Rate Limiting. So they're called Global and Local Rate Limiting. And the terminology really comes from the fact that, you know, usually when you deploy Envoy, you're not just going to have a single instance of Envoy. You typically are going to have a kind of a fleet of Envoys, multiple instances that are running. And so if you're running a service mesh, you might have an Envoy sidecar per workload. Or if you're in an Ingress scenario, like you are with Contour, you're probably going to have a daemon set or a deployment that has multiple instances of Envoy. And so then the question with Rate Limiting is really, when you're making a Rate Limiting decision, is it taking into account all of the traffic that's coming into all of those Envoy instances, which would be kind of a global Rate Limiting decision, or is the decision made locally by an individual Envoy, just based on the traffic that that Envoy has seen coming in without any coordination with other Envoys. So that in a nutshell is kind of the difference between the two approaches. Like I said, Envoy supports both and Contour supports both. The key operational difference is that with global Rate Limiting, you, the user are required to deploy a separate external Rate Limit service that's responsible for making those Rate Limit decisions. And then each Envoy within your Envoy fleet is going to be communicating with that external service, providing some information about requests coming in and getting Rate Limit decisions back. And then global also provides you some additional flexibility in terms of how you Rate Limit. So you're able to Rate Limit by things like the client IP and header values on requests and various other things, whereas local Rate Limiting is pretty simple and basically just allows you to limit the total number of requests that hit a backend service through any particular Envoy instance. And so just to dig into the global Rate Limiting architecture a little bit more since there are some more moving pieces there. What you see here, first of all in the center in the purple box is Envoy. And then on the bottom we have the Rate Limit service. So as I mentioned on the previous slide, this is something that you as a user would have to deploy yourself. Envoy publishes a GRPC interface that the Rate Limit service is required to adhere to. But as long as your implementation meets that interface, you can use whatever implementation you want. There is an open source Rate Limit implementation that's published as part of the Envoy GitHub organization. So that's definitely an option for you, but you're not tied into it by any means. And so then on the top in blue we have Contour. And Contour is kind of made aware of the existence of the Rate Limit service through an extension service, custom resource. And this is a part of the Contour API that we introduced as part of the external auth work last year. And so this tells Contour that the Rate Limit service exists and should be configured with Envoy. And then each of your HTTP proxies within Contour can optionally define a global Rate Limit policy, which essentially says that information about requests for that proxy should be sent to the Rate Limit service and the Rate Limit service should then return a Rate Limiting decision back to the user. And so Envoy then, as it's processing requests coming in, will reach out to that Rate Limit service, provide the information about the request, and then based on the decision that the Rate Limit service makes, either allow the request to proceed to the backend service or return an error code to the user. So with that I'd like to jump into a quick demo of global Rate Limiting. So let me switch over to my terminal here. So first of all, I have a cluster here that's running a three-node cluster. Give it a second. So I have a three-node cluster here and let's take a quick look at what's in the project contour namespace. I get pods. And so you'll see I have my two contour pods as part of my replica set. And then I have an Envoy daemon set, so one Envoy per node. And then additionally I have this Rate Limit pod here and this is part of the Rate Limit service that I have deployed into my cluster. And then let's just take a look at the contour config map. And this is where you as a contour user would tell contour about the existence of the Rate Limit service and so you can see I just have a simple YAML block here that defines the Rate Limit service. It identifies the extension service that kind of maps to that Rate Limit service and provides some additional parameters for that Rate Limit service. And then the next thing I want to take a look at is the config file for the Rate Limit service itself. And this is where the actual Rate Limits are defined. And so I'm not going to get into the details of the exact configuration format here. This is specific to the Envoy Rate Limit service, but if you have a different implementation, your config format would look a little bit different. But the important thing I want to point out here is that we have two different Rate Limits defined. So the first one here, you can see that there's a five request per hour Rate Limit and that's defined for each remote address, which is effectively the client IP. So this is saying that each client IP can have five requests per hour. And then the second one is similar, so it's a two request per hour limit. But it's saying that if this, essentially if this header value here is present, so if X Contour Rate Limit is defined on the request with the value of true, then only two requests per hour should be allowed. So basically if the header is present, you should get two requests per hour. And then in total, each client should get five requests per hour. And so the last thing I want to show just before I start issuing some requests really quickly here is the actual HTTP proxy I have defined. And I just want to focus kind of on the Rate Limit policy. So this is a new part of the HTTP proxy API. And so you can see here that I have a global Rate Limit policy defined. And again, I'm not going to walk through this in excruciating detail, but this is basically telling Contour and Envoy that for any requests coming into this particular virtual host, we should send the client IP to the Rate Limit service and then if this header exists on the incoming request, we should send that to the Rate Limit service as well. So what I'll do now is demonstrate those Rate Limits being enforced. So the first thing I want to do is use that two requests per hour Rate Limit. And so if you'll remember, basically if this header is present on the request, we should only be allowed two requests per hour. So I'm going to issue my first request here and we can see we got a 200 response. Everything worked okay. We got a response from my Echo server. And so I'll do one more request and we see we get another 200. And so now I've issued my two requests. So this next one should be Rate Limited. And so we get a 429, which is a too many requests response. And you can see a number of headers here that describe some information about the Rate Limiting that's taking place and tells you that it's been Rate Limited. But we know that if we don't have the header, we should be allowed five total requests per hour. Now, I've already issued three requests and those have counted against this additional five requests per hour quota. So I should be able to issue a couple more requests here where I get a 200. There's another 200. And now I believe on this one, I should get Rate Limited because I've now issued a total of six requests from this client IP. So hopefully that gives you a feel for what Global Rate Limiting looks like in Contour and Envoy. There are many more knobs and many more ways to configure this that I don't have time to get into, but definitely check out the docs and play around some more if you're interested. And with that, I'll flip back to the slides and hand it off to Nick. Hi, everyone. So I'm talking about the roadmap today. So we've got, you can see here that there's a few, this is the bigger items on our roadmap. Our whole roadmap is public and it's published in our Community repo. There's a link in the slides if you can see it. But if not, it's github.com slash projectcontour slash community. And then there's a roadmap.md file. So the first thing we've got here is we want to bring, we want to get our operator up to scratch. We want to get it all the way to GA, obviously. We make it beta first. It's currently alpha. In my mind, you know, I think we've talked a little bit about this, a large part of the things that we need to graduate to GA, the biggest feature that we need to do that is support for upgrades. The operator is intended to help you operate Contour. That means it helps you install Contour. It helps you make sure that it's, that it upgrades to the latest version and it should do that upgrade in a safe way for you so that you don't have to encode the knowledge of how to do a safe Contour upgrade into your deployment tooling. The operator can do it for you. As part of that, we also want to, and a little bit associated with that, we want to expand the Gateway API support. We want to make sure that we bring that to as production ready as we can make it. Obviously, with the Gateway API still being an alpha API, there's a limit to how far we can take that until it moves up. It's the production readiness chain itself. But I think that we should be able to get good support for the basic workflow and the two route types that we support, being a HTTP route and TLS route. We should be able to get those in a reasonably timely way, in a few months, hopefully. That's what I'm hoping for, anyway. The next one I wanted to mention here is, we've definitely had some issues with this in the past. Contour currently has two options for the code that actually handles XDS. XDS is the control plane protocol that Envoy uses to talk to its control plane. If you are deploying an Envoy in your cluster, you are running a control plane. It may be a static control plane from a file, but if you're running any of the other products that use Envoy, they provide an Envoy control plane. Currently, Envoy Contour supplies two options for that. There's our own organically homegrown, slightly elderly implementation, and there is one based on the upstream go control plane implementation. The homegrown one, it is aging, as I said. There's been a few advances in the XDS code that we haven't had a chance to build out yet, supporting things like incremental XDS and the ADS Anything Discovery Service, basically, and a few other things there. The reason to do those is that it should help when you're running a large contour installation. We have heard from people who are running thousands of HTTP proxies that Envoy can use an awful lot of memory in that case. We're hoping that by modernizing the XDS code, we should be able to help a lot with that. The last thing that's on the roadmap that we always intend to keep pushing along with is the further feature work. Some of the ones that we've got in-train, we've got some work for ALS, which is Envoy's automatic logging service. You can configure a remote logging service to have Envoy send all of its logs to. There's a few things like tracing and other stuff that's well-requested features that have been around for a while. The requests have been around for a while, and we are now working our way down to getting to them. With that, I think I've hit as much as I can in the time that I have. I'd love to take more questions about this at some other time. Over to you, Alex, for to sum up. Yeah, okay. I just wanted to also add that we're also working on Windows support in our roadmap, as well as making sure that Contra can deploy onto IPv6 clusters. These are the two big ones. Thank you, Alex, for doing your PM job and making sure that I get those things. It also fits compliance, which is a lot of customers have requirements. Open source users, community members as well as customers have requirements around delivering FIPS 140-2 compliance images. They can show that Contra works using a specific set of TLSI for suites. So all of these are coming. Yeah, the last thing is the community. The community is doing really well, as everyone can see. So we're at 2.7k GitHub stars. We have really lots of contributors, 450 forks. We have maintainers from VMware, from Red Hat. We're taking a very active position in driving the design for the Gateway API project upstream. So a few ways to reach out to us. You can reach out to us on Slack in the Kubernetes channel. You can also follow our Twitter account. Find us on GitHub at Project Contra and watch some of our community meetings as well as office hours on YouTube. So yeah, if you guys have any questions about Contra or the project, if you're, like I said earlier, if there are needs around Ingress that are not being met today in Contra, definitely reach out to us so we can discuss them. Anything else from anyone else? I guess I'd just like to say thanks to everybody who's contributed in the last few months since we last gave an update. It's been amazing to see such great contributions from the community. It's been really great to bring Daniel on board as a maintainer that's not from VMware and to just start getting a lot more external contributions. So as a take later Contra, I tip my hat to the community. Not actually wearing one, but you know what I mean. And yeah, just thanks to the community for everything we're doing, and we're really excited to see where we go from here. So I think we're going to move to some questions and hopefully we'll talk to you soon. Thanks for attending, everyone.


Okay. So how many of you submitted PA2? Okay. Are you feeling proud of yourself? Well, you should. What you've done is a better implementation of coroutines or also called generators than what Python has. When you study for the exam, you will see the semantic differences and you'll see how the Python creators cheated to get them implemented. So what do you have? As you will see, it allows you to write much nicer, much easier to write generators and lazy iterators and all that stuff than what do you have to do in Python. So good for you. So what we are starting today is essentially a milestone. Building on what you did with coroutines, we are going to go deeper into the territory of programming under an abstraction. What I mean by that is we are going to build constructs that other programmers can more conveniently use. So rather than just being ordinary programmers, we'll give tools to programmers so that they are more productive. So what we've done so far is use these coroutines to build iterators, lazy lists. If you look at homework 2 already then regexes and backtracking. So today we'll go further and build on top of coroutines a prologue interpreter. So since you are doing so well, you can implement your own coroutines, we are not going to actually give you an interpreter for prologue. We are going to guide you through most of the steps, but the actual implementation of the prologue interpreter, you'll have to invent yourself. So this is a crucial lecture in that I'll try to teach you how to think about the problem so that then the last crucial step you can develop yourself. A needless to say PA3 is assigned today, it's Tuesday, so we are starting again another deja vu. So what we'll do today, think of it more as a discussion section, we'll have a bunch of problems to solve that will take us to the interpreter and get a paper and pencil and start getting ready for talking to your partner. So a prologue refresher, these are problems that Tbo, one of the TAs invented a few years ago. These are a few facts that show what Tbo likes to eat.  So if you ask the query, would Tbo eat the lion? The answer is, the answer is false or fail or whatever your interpreter answers. If you ask eat Tbo X, what would the answers be? There would be two answers, one of them would be vegetables, you put a semicolon, the second one would be fruits. Then you do a semicolon and then I think it will say fail or none or something. Signifying there are no more answers. So far so good. I could not answer an important but a simple question last time. I don't know where Rohin is but maybe he'll show up in a second. So I'll try to answer it in a much more reduced simple example. So look what I modified in this program, the refresher program. Can somebody describe to me the single change I've made? There's something in bold but the bold of course is not significant for the interpreter. Something else is significant. What is significant? So is it a keyword really? It is bold so I see why you may be confused that it's a keyword but it's not really a keyword. What is everything? It's a variable because it starts with a capital letter. So that doesn't have any special meaning. It's as good as X. I could have said X. Now if I ask this query what do you think the answers will be? The first answer should be simple, right? What would be the first answer? It would be vegetables. Now I ask the semicolon for the next answer and what will be the answer now? Okay? It would be an unbounded free variable. It would be essentially some internal version of everything. Let's just call it underscore everything because we will see today that the interpreter renames these variables for a good reason or you will see that in building the interpreter but essentially it binds X to this everything and everything is not bound to anything so this is the best answer it can give you. It's also sort of the most general answers. Signifying that if you ask a query, eat, tea, bo, foo, it will be a true query because according to the facts we have, tea, bo eats everything so it's foo as well. The problem we saw last time was a little bit more complicated because we had these nested facts like cons of something but essentially the principle was the same that yes we can answer the query in the affirmative but we have nothing more specific to bound to X just another variable so the answer is X can be bound to a variable. So that should answer that. Now one thing we didn't get to last time are lists. So what is, if you look at lists in prologue, essentially prologue gives you this notation for lists. Okay? Gives you this for, this would be a head. This would be the tail. It's a special syntax. There is nothing magical going on underneath. They are using the sort of nested predicates to build lists which are just essentially lists of elements nested within one another and these are, this is how you can define car, cuder and cons. If you are a scheme or list programmer and you're not familiar with the bracket notation, you want to use your car, cuder or cons notation because that's familiar to you. This is how you would define it. So let's just look at car. If the first argument is a list, you would like the second argument to be bound to the head of the list. Okay? What happens here is that the list is decomposed into head and tail and then this value here is bound to X. Cuder again decomposes the list but binds the second argument to the tail and what is cons? Okay? Cons takes a head and a tail or X and the rest and creates a new list where R is the tail and X is the head, essentially a prepending another cons element to it. So these definitions are nothing more than just finding another name, sort of aliases, cons, car and cuder for existing lists. Okay? Does that make sense? So I'll let you look at some of these definitions, look at say car and try to understand how that works. So remember when, let's, let's do this example. I pass A, B, C into car and I ask about X. What would be the answer here? Okay? Yes, X would be bound to A. If I ask about cuder of this list, X would be bound to B and C. Okay? So let's hope this is clear because we have a few examples with lists coming. So here is an operation on lists. Okay? You want to ask whether an element is a member of a list.  The bracket notation is sort of like a pair except you could use in the bracket arbitrary number of things. So really what the bracket notation is, this here A, B and C really is desugared in a familiar manner to A, B, C, an empty list. Okay? Which really is the same as saying I have A, B, C. And now I believe they use some special, I'm not sure what comes here. Maybe this is nil. Some special atom, some special name. Okay? So the first desugaring still stays within the special syntax of brackets. But if you look at this, this is a pure prologue. Remember what is prologue? It just has predicates which can have arguments. And this is a special predicate with this funny name dot. Right? We could call it full. It would be the same. They just use the dot. So this is really the translation that you see that is going on under covers. And if you're familiar with syntactic sugar, you should understand that prologue really doesn't understand anything about lists. Right? The parser does, but the interpreter doesn't. So to get you familiar with lists, here is a definition of a member function. It's recursive just like it would be in C or scheme. And what does the first case says that, well, x is a member of a list if it is in the head. Okay? Or x is a member of a list if it is a member of the rest of the list. How do you obtain the list value? Match on this, you extract the rest, and you do that. Also, because this is logic programming, you can think of it this way. You can say, well, if x is a member of the rest of the list, then it is a member of any list that contains anything in front of it in the head. So again, if x is a member of a list R, then it is a member of any list where y is prepended to R. So you can think of it in whichever way procedurally or declaratively either way works. All right. So here is the list append, and now where things become a bit more fun. Okay? So here is a predicate that takes one list, another list, and appends them, concatenates them. Okay? How do we do it? Well, the base case is simple. You say, well, if I take an empty list and another list, the result is what? The same list, right? Okay? So that part is easy. Now, how about the recursive case? Well, let's look at this. We take a list, decompose it into head and tail. We'll take x. What is the result? The result will be a new tail. How do we obtain that? Well, the result is actually this. It's new tail with h prepended. Where does this h come from? It comes from here. Where does this tail come from? It comes from here. Actually, I probably made it worse with my line. So let's just look at that. One way to think of it is that you take a list to which you want to append x.  You don't do anything with x. x is unchanged. Except when you get the result from here, you put it in here, and you prepend h next to it or in front of it. So again, what does the recursive thing do? Strip the head, obtain the tail, recursively call tail with the same x, no change. You obtain the result, you pass it up here, prepend x, and this is the whole thing is the result of the computation. So the colon dash here means this is essentially, you can think of it in two ways. You can think of it as if this holds the right-hand side of the claw. So this is our right-hand side of a claw, and this would be, of course, the left-hand side. If the right-hand side holds, then you could say the left-hand side holds. So you can think of this as an implication. Another way to think of it is that if you are trying to answer a query, the query will match to the left-hand side, binding the variables. How is the query answered? Well, you go to the right-hand side and recursively answer the right-hand side. If you can answer the right-hand side, then you indeed have answered also the left-hand side. But you can also think of it as a procedure call. You sort of call the left-hand side that translates to the call of the right-hand side. So look at that because a pen actually shows quite a few subtleties of prologue. It is one of the beautiful two-line predicates that do a lot of work, show quite a few principles. So what would be the answer to this call? What would be X? Well, we strip A and then call tail with B, which then in another recursive call strips B and ends up with this base case, where the first list is empty, X, or this is CD, that propagates back up a few times this way. First we prepent A, then we, sorry, B, that we prepent A, and then the result ends up being A, B, CD. So one thing that I told you here is I gave you this procedural view, which is if I pass here the list, like A, B, it is decomposed into H and tail being this list, and then you call the right-hand side. And I even showed you that X flows from here to here and tail flows from here to here and new tails flows from here to there. So some of them flow from left-hand side to right-hand side, the other way around. But it doesn't need to be that way. What happens if I make this call? So indeed the answer is CD, but the important thing to remember is that what this rule says, it binds this and that new tail together, this X and this X together and this tail and this tail together, but the flow could be this way also that way. Similarly it could be in either direction for all of these variables. And in the first query the flow went one way, in the second query the flow went another way. So in a sense what we have is a bidirectional programming because these variables can sometimes act as inputs into the entire operation, sometimes the act as output. So a single rule for append can compute X from these two arguments or it can compute X for these two arguments. So to make sure you understand it, let's see. So what if we do this? Okay, this is clearly one answer. Are there multiple answers? Yes, how many answers would we have? Somebody said five. Indeed these are the five answers we would get from append. And so a warm-up exercise for you is find a query that, given the definition of append, will create infinitely many answers. So so far we had four answers, but we want now a query that if we enumerate the answers the whole process will never terminate because there are infinitely many answers. So what would that query be? So I can go back to the definition of append so that you see it here. So this is the time when you don't just think really hard because thinking hard is really hard. But you talk to your neighbor and you try to convince her that yes this is the query and this is why it has infinitely many answers. Okay, so how many people have or think they have an answer or have a guess of an answer? Okay, I wasn't sure myself until I tried it in the interpreter. You have not tried it so you can have low confidence. All right, so should we try? What is your query? I see. Okay, so let's actually try it. Let's actually try it. Now I just need to find this. So I have this append. Okay, so we'll do append and empty list and x and y, right? So it has only one answer, right? Is that what you meant? Because essentially what it says that if you append anything to an empty list the answer must be that anything. So essentially it says that x and y must be the same. So it has essentially, you are correct that this answer really represents many different answers because whatever I put for x will be a correct answer for y, right? So you are correct that I can instantiate these variables x and y in infinitely many ways and it is still correct. But this single answer from Prolog represents all of them. So in a sense I, you're correct I didn't specify my question precisely now.  But you are correct too in that this does indeed have infinitely many instantiations. But you see it was sort of smart. It said I can describe it one answer all possible and results and I can describe them by saying x and y must be the same lists. All right. Okay, so this is one answer. So what it does, it now creates lists of arbitrary of all possible lengths. It doesn't know what these variables are, right? It could be anything and the way to say I don't care what the elements of the lists are and I specify that I don't care by inventing a fresh variable that is not bound to anything. Excellent, excellent. My answer was a bit different but it was essentially the same. I just put variables everywhere. All right. So play with it. By all means this is fun, especially look at some fun examples from tutorials, work at them. So I would love to instead of teaching you how to do the interpreter go through these examples because some of them can do computing a derivative of a function by you describing the derivative rules for differentiation and given an input expression it will do the computation for you. It can then sort of solve a math problem not through math algebra. It can do too but it can do it by just plain search. Like plugging in plus and minus between numbers is a problem I solved this morning with my son. It could do it by brute force search rather than by reasoning and brute force search is elegant when somebody else does it for you and does it fast enough. All right, so let's move on please. Here's eight. The interpreter is faster. So let's go to the business of building the interpreter. So what happened during the execution? We were talking about matching, matching a query to rules and so on. That process is called unification. As some of you pointed out it was covered in 61a. Well this class is essentially just 61a on steroids except we cover 61a in four weeks and then all health breaks lose. So unification takes two terms and try to see whether they are compatible so to speak. So are these two terms compatible? Yes, no? Okay, so if the one on the left, if this was a fact, okay, if this was a fact and the second one was a query, what would be the answer to this query? The answer would be x equal one so it would be true. It would be x equal one and it would be a correct answer because given the query you can find a matching compatible rule. Okay, why are they compatible? Because there exists an instantiation of these variables x and y which makes them into identical terms. What is that instantiation? Well, what does y need to be? What does x need to be? Well, y will be two and x will be one. If I do this substitution I'll end up with two identical terms so they are compatible. Okay? How about these two? Are they compatible? No, they are not because there is nothing I can do with this a and b. They are not equal. So this one is no. This one is yes and here is the substitution. How about this one here? It's no because one is different than two. This no because a is less different than b. How about this one? Yes and the substitution is you'll make x equal to y. All right. So imagine we have a call to a unify function. We'll give it two terms. We'll do its work and say not compatible, not unifiable. If they are unifiable it will return the most general unifier which is the substitution. It's most general in the sense that well it could return a particular substitution that will make them equal but we want the most general thing. For example, a unifier here could be x equals y equals one but this one here is more general because it has more possible substitutions that you can plug into them. These x and y are unbound. They are not specific. Okay, so make sure you understand it. Discover whether these two pairs are compatible and produce the MGU if they are compatible. So again, work together. Unification is sort of a boring part of the whole thing but we need to understand it so that we can then go to the actual crunching that the interpreter does. So again, work with your partners. Work it out, I'll sample who has the right answer. There is a lot to talk about about these two problems. So if you are not talking about anything you should be. All right, so let's start with the first one. Are these two terms unifiable? Yes, all right. Can we get the MGU? So x would be equal to b of c of underscore z. Who agrees with that? Another attempt for, yes, please. You are agreeing. Okay. Oh, okay, I see, I see, I see. Okay, I actually missed it myself. Any other substitutions that we need to make? How about y? This would be c of underscore z. Okay, okay, I missed something here. So one way to, you can see what's going on is to draw it this way. This is the left term. The right term is a b of y and c of z. Okay. And we sort of start matching them top by top and we get a match between a. So that's fine. Now this x must be unified to this, right? And y needs to be unified with that. And this clearly is unified as well because it is the same variable. Now it is a correct answer. Is this the only way how to write this MGU? There are clearly other ways how we could write the same unification, right? The same constraints. Well, how about if we say x is equal or maps to b of y, y maps to c of z? Would that be the same? So here is one MGU. Here is another one. Are these two essentially the same? Syntactically, they are not the same. Clearly, these are different terms. But do they encode the same constraints? Right. So they are the same and exactly for the reason is that no matter what substitution you put into these variables, sort of ground these variables. If you say x is one and y is b and z is something else, whatever satisfies one satisfies the other and exactly the definition for y they are equal. So there are multiple MGU's but they are really unique in the set of constraints they encode in the set of substitutions that they permit. Great. So this is fine. Now how about the second problem? The little problem here. Are they unifiable or not? And now here is an opportunity to be religious about this because there is no true answer. So we could really divide into camps and keep the rest of the lecture arguing. So what do you think is the right answer? So if x is bound to an empty list, well, let's try it out. So if I put here an empty list, I'll get here this on the left. This one here is A and so they are not different. So x is not an empty list that really produces different results on the left-hand side and the right-hand side. So who thinks they are unifiable? All right. I said you are correct. What can I say? Who thinks they are not unifiable? You're also correct. So if you think they are unifiable, then clearly we need an MGU from you. So what is that? x would be a stream of, oh nice. So x is a stream of infinite ones. So that's a legal answer. So who thinks that they are not unifiable? Now it may be harder for you to disagree since it seems like we do have a counter example. So the response, by the way, we didn't hear it, that in the context of a language can we encode such a stream of infinite ones and really to produce a quality? Think about that while we hear another point. So you could encode it with essentially an infinite predicate that generates that. Now, yes we could, but the thing is that they designed or decided to encode unification in the context of prologue such that you need to find a finite substitution for it. And now we need an infinite one to really show that the terms are unifiable. So there does not exist a finite substitution that makes them equal and therefore we will consider them not to be unifiable. But in another language, yes you could, except in this one it is not. So I think the answer here is not in prologue because the MGU or I should say the substitution must be finite. Okay, that's great. I love that. So if you want to read an algorithm for doing unification, a great write-up is in the book from which you will have a required reading. In fact this chapter is part of the required reading, so why am I advertising it? And it's a simple description of how you walk top down through the tree, push the goals on the stack that you still need to unify, and there is a nice example. We don't need it quite for the rest of the lecture, so I'll go directly to how I will try to teach you to implement the prologue interpreter. We are not going to just look at one interpreter and I'll leave a few things for you. We are going to walk through a few interpreters and we'll do it by building an interpreter for a subset of prologue, in fact different subsets of prologue, and by sort of going to stronger and stronger languages we'll learn how to handle this aspect and another aspect and hopefully at the end you will know how to do it for the full prologue. So we'll organize these languages in a matrix and we'll divide them based on how many rules they have on the right-hand side. So this matrix has just one. This one can have an arbitrary number, okay, and here is what we'll do about the choice. What choice I have in mind you see soon, but let me just say that in these two no choice will be needed. Here the choice will be made by an oracle, so we'll rely on somebody doing this for us, and here we'll actually implement the oracle with backtracking. So we'll have six matrices, we'll walk through them like this, so cover five of them today, and of course the hardest one is your programming assignment, but you'll be ready to do it. So here is what the languages are, so look at them and you will see what I mean by having to make a choice versus not having to make a choice and what I mean by the number of rules on the right-hand side, right? So if you look here, there is only one rule on the right-hand side of, one goal on the right-hand side of these clauses, whereas here we have one, two, one, two. So the interpreters here are going to handle programs with multiple rules on the right-hand side, here only one, okay? Now if you look at those, here we have a choice between c2 and c1, so there are multiple c's here, same for here, whereas here every predicate has only one choice on the left-hand side, right? There is one a, one b, one c, and that means the interpreter doesn't need to make a choice between them, it just finds one. It seems like that cannot possibly make any difference, but it does, and in fact this is where most of the complexity in your implementation will come from, being able to handle the fact that there are multiple choices. Can you guess why this will be tricky? Well it grows exponentially with the number of clauses, but the cost will not trouble you as much as the fact that you have to implement it. I think yes, it will be exponential if this, indeed this is the complexity of prologue, but the fact that you need to iterate over all these choices and consider one, and if it fails then consider another one, mean to build backtracking to do this essentially return and consider the next choice, this is where the complexity comes from, okay? And which is why I want to walk you through the simple cases first, so that you understand things aspect by aspect, okay? Now the orange algorithms are going to be deterministic, which is to say the algorithm does all the work, the algorithm prescribes what happens next, those in the middle will get the help from the oracle. The oracle will just make the right choice of the rule for you, and this is still an interesting algorithm, we cannot run it without somehow implementing the oracle, of course, but it will be nice to look at the algorithm and say, oh, if somebody made the right choice here, I know what the algorithm would have to do. So let's start here, and what we want to handle are programs where on the right hand side we have simple rule, one goal, and we do not have choices, so there is only one C, one B, one A, all right? So what I want to teach you first is what's a proof tree, essentially this is just a trace of the execution. So if we have this program which you just saw, if I ask this query what would be the answer? Z equals one, of course you know that, but now try to think how that answer was produced. I'll have on the right hand side of the slide soon essentially a trace, a visualization of what the interpreter had to do. It was the same as you had to do in your head, so that's a good thing, but try to visualize it, so what happened during the answer of the query?  Well, if you can concisely say what happened this would be great, so please go ahead. Okay, so effectively we go from, we'll say, well, C of one we know is true, hence C of y is true for what y, for y equal to one, okay? From that it follows that B of y is true for what y, y equal to one, and from that, right, we have proven that this holds, now we are following this, then this holds, and then that holds, right? So we have these implications. This holds A of x for x equals y, and hence A z holds for z equal to one, right? Essentially this is the derivation we made. How did we make the derivation? We couldn't. We, the interpreter, just look at the code and say, oh, here is the chain of implications, right? We had to find the right chain of implications. How did we find it? We'll build some graph and we search the graph. The graph doesn't need to explicitly exist, but we could think of it as existing, right? And here is indeed the proof tree. So the proof tree was essentially constructed by recursive invocation of some actions, and I can tell you that the execution went like this. During the execution, we have constructed that, and then as we went up, we constructed something else. And you may be surprised why it's a tree. This one is not tree in particular. It's a chain. The reason is that on the right-hand side of every rule, we have only one goal. If there are multiple goals on the right-hand side, this is when the tree would become a true tree with multiple branches. But what I want you to do is look at that visualization of the tree of the proof process, which is really the execution of the interpreter, and try to understand what happened during the execution. I can tell you there are two kinds of steps that took place, okay? Can you find where these two steps, one and the other, were applied, and what do they achieve, right? So what I have here is going down the tree. There are two kinds of operations we took. Can you spot where they were taken? I want people to think about that, because once you understand that, you have an algorithm for the simple version of the problem, then we'll make it more powerful. Because getting this algorithm right is an important starting point. So we want these two operations as we go down. Okay, so let's stick with that. I'll hold the thought about that. So the first one indeed is what you described. The process of matching variables inside is really nothing different than unification, right? So the answer is we always have a goal. The initial goal is what? What would be our first goal? What goal do we start with? Is it like the first predicate in the program? What do you think will set our initial goal to be? I'm sure people know. How many people know what's the initial goal? Okay? The query would be the initial goal. This is what we want to answer. Is this true? Okay? So we'll start with that goal, and we now match it against something exactly as you described, exactly using the unification algorithm. The query is what? A name of a function, some arguments inside. We'll match it against what? We'll match it against these heads of clauses in our database of facts, right? So we start with this query, okay? And we'll match it against what? We'll match it against this. Do they unify? Yes, they do, right? We obtain this information here. We have now unified x and z, and we have changed our goal from this to that. Now, a of z is true if a of x is true. We have essentially reduced our goal from the initial goal or whatever the current goal is to the one we matched it to. So we reduce this goal here to that one through the process of unification because they are the same thing. They are unifiable. And this is the MGU of the unification that happened in here, right? So far so good. Okay? So what we described is exactly one of the steps. We take the current goal and match it against the stuff on the left hand side, the heads of clauses. There are other places where this happens. It happens also here and here, right? So these are, I'll do a legend. This is match current goal against heads, okay? So we are done with half of the steps. What are the other half? Can you say what the other operations would be? Yeah, the matching happens, but the remaining steps that we have not understood, such as going from a of x to b of x, what happens there? So what happens in going this way and going this way? What happens here? What are those steps? Exactly. We'll essentially replace the left hand side with the right hand side. Say, if I can prove the right hand side or if this is true, then the left hand side is true, all right? So this here, what I visualized that way is you could say goal reduction. So now we have these two operations and we go down and as we do these steps, we compute these MGUs, right, for each of these steps, okay? These MGUs are created as we match goals against heads. Then we go up, we'll merge these MGUs. And eventually, we get the final one and this is a projection to the result, project the result, right? Because we don't really want to show the programmer all the intermediate variables like x and y, but she only wants to see the z. So this handles only the simple case of one choice on the left, one goal on the right hand side, but you will see how the other algorithms are just generalization of this a little bit. So what I want you to do now is essentially write down the algorithm because I really want you to understand the other generalizations. So let's go on. We talked about that. Here are the two traces of running it, but I think you understand that. So I'll leave it just for the slide. So now take a paper and pencil and write the algorithm. I'll just flash it for you. It's really short. So it is maybe five lines. To make it simple, I want you to do the same cheat as I did. First, write the algorithm such that you completely ignore the business of MGUs, the fact that you need to merge them on the way up. It's easier that way, and then add the handling of MGUs. So take a few minutes. It's a good investment. You really do write it down. I would like to get a volunteer to write it on the board. It will be nice if there are some mistakes because from those you really gain the understanding. If there are no mistakes, it's okay because I'm sure my code has mistakes in it. You can learn from those. Okay, so who may be ready to write an outline here on the board or directly on my laptop? Who feels comfortable enough? Remember, you get five bugs for free, so you can't fail. You guys feel like writing it up?  So who feels like they know how to do it? Okay, that's great. Come here. Do you have pseudocode on the paper? Come here. I'll write it down if you don't feel like it. Sure. This is recorded, but there is no camera, so you won't quite get famous enough. All right. So we are doing for each B on the left hand side. Okay, so let's write it down here. For each B on left hand side. So for you, how about if we say this? For each head, H of A clause. So we are walking through the clauses and picking up every head. So the thing on the left hand side, let's call it the head. If unify A and B, and then write. So we'll do if. Okay, right. So we'll do something like process A, which is let's say the type of this is our goal. If unify A with H, then we do what? We succeed. So we'll unify somehow. We'll say A to the head. So head becomes our new goal. Okay. So essentially this is our, let's write it this way. New goal is H. Okay. And we break out of the for loop. So now you want to take the right hand side and do something with it, right? So we started with A, we matched it with head. And now actually the next goal would be the right hand side. All right. So we could say, well, we have one new goal and then the next goal actually will be you say the clause C, the right hand side of that clause. There is only one goal that's guaranteed by the restriction we have so far. Okay. Fine. We recurse. Perfect. So we'll do process new goal. All right. And if it doesn't unify, else we'll do something like return fail. Okay. And we also need a base case, which is when? So we need to do something like if no right hand side, then we'll do return something like, okay. Thank you. So is this reasoning fine? Do you see a problem with that? So we start with the goal A. We match it against the left hand side. If we do find a match, now we need to decide. Does it have right hand side? If yes, that is our new goal happened here and we recurse. If there is no right hand side, then we have reached a fact rather than a rule. And the fact is true. We can return okay. If we didn't match, then we have failed. And that failed will hopefully propagate up. Maybe we need to tweak it a little bit. All right. So do we see some problems with that? Well, technically speaking, it doesn't have to be because remember the restrictions we have now is we can match with only one head. Oh, I see. I see. Okay. That's true. This needs to be outside four. So the four loop is between here and here. Okay. Excellent. Yes. So when we go over all heads and we did not match, we fail. All right. This recursion here should probably say that recursively call process and whatever it returns, you return. Okay. I think we are pretty good. So here is how my code looks like. We start with the goal. We match it against a head of H of a close C. See, I do not have a loop here because I'm assuming here that there is only one instance of each predicate. I don't need to go through them and see which of the matches. It's the one that I can directly find. Remember the restriction? I don't need to make any choices. If my goal is A of something, I'll look for that one A and I'll match it. So I don't need to have any loop here. Okay. That is my simplification. There will be one match, exactly one match. Now, if no matching had found a return false, if I did find a match, but there is no right-hand side, I have found a fact. And otherwise, I recurse. I should probably say return here. So is that correct? Right. So this one is incomplete in the sense that it has no MGUs. Now, let's go to the next slide. And here I have an MGU. So when I match my goal, say A of X be the head H, which might be A of Y, then I get the MGU, which is X equals 2Y. That's my MGU. The rest is the same, except I return nil for fail and MGU for success. And when I call it recursively, I get the MGU back and what I return is a merge of these MGUs. There might be a mistake here, but I think it captures it all. So very simple extension. So what has happened here? It's a simple recursion. We just have a goal. We know we match it against exactly one. The match produces an MGU. Then we go to the right-hand side. That's our new goal and we recurse, recurse until we reach effect. If we reach effect, we are done and we just collect these MGUs on the way back. Those propagate whatever constants we have in the base fact all the way to the answer and that's it. And this is indeed the algorithm that I believe we gave you in PA3. At least that was the plan. This is what runs and you can now start with that. The resulting algorithm will look very different. So don't think that you can just add a statement here and there, but this one runs. Does this work for clauses that don't have effects? Yes. So clauses that don't have effects are rules. They have left-hand side and right-hand side. It does. In fact, here is one. If you have no right-hand side, then you have found a fact. You could say you could found a fact. If it has right-hand side, then the right-hand side here is the new goal. So it does work. Here is the base case that returns an MGU. I see you asking whether it works for cases that don't have facts. I see. No, yes, that would recurse forever. You need to have a predicate that ends with a fact. Sorry, I misunderstood. Yes, a fact can have variables indeed. Exactly. So this will work correctly with the case when the answer is, for example, the variable from your query unified with some fresh variable from the interpreter. One thing that this algorithm doesn't do, which is important, each time you encounter a new rule, which is here and you make it your new sub-goal, you need to rename the variables. Can you guess why you need to rename these variables each time you encounter a new rule? What would happen if you don't? You get collisions because these rules could be recursive. Then these MGU's, which you want to collect on the way up, would have multiple copies of the same variables, and they would essentially collapse facts that should not be collapsed. So that we are not showing, but it's important to do that. Let's look at this new language. This is still not a general prologue. It can have multiple rules on the right-hand side, but we cannot have multiple facts, multiple choices, or multiple rules. So what extensions are we going to make? I want to introduce two facts, two sort of two new concepts. One of them is a resolvent. What is a resolvent? In the previous square on the left, we had always just one current goal. Now we are going to have multiple goals, right? Because when we match against the head and we go to the right-hand side, there are multiple two, one, two, or more goals. This will now become all goals that we need to solve. So now there isn't a notion of one current goal. There is a notion of multiple pending goals that need to be answered. That's called a resolvent. And they form a stack, these goals on the resolvent. And you can think of it as a conceptual stack that you don't really need to implement. Maybe you'll find it convenient to build it with an explicit stack. But at least think of it as a stack because what happens? You pop a goal from a stack. You find a matching clause for a goal exactly as we already know how to do. If the popped goal is answered, we go back to step one. If not, you push the goals from the right-hand side of the stack and you go back to one. So the stack is nothing else just keeping those pending goals. So the conceptual stack could be real, could be different. Okay? So think of the resolvent as the set of pending goals. And so now I want you to write an algorithm for this language, which could have multiple goals. For your reference, here is what we developed for the case of no, for just one right-hand side. So you can look at that and think how you would extend it. Now we want these extensions to be minimal, ideally one line change, two line change. So think about this and how would you change it so that it handles the multiple right-hand sides. And don't feel forced to use a stack. The stack might be a conceptual thing that is handy to use in drawings, but you may not want to have it in the implementation. So how many people know the answer? Okay, we need more. So think about what has changed compared to the previous one. The only change is that now the right-hand side here, so this is the case that handles right-hand side. Now this right-hand side could have multiple goals, more than one goal. Before it was always one. So the delta is that it can have more than one goal. So what would you change? How would you simulate this? The popping from the stack of the goal, resolving it. So we could potentially take the right-hand side, which is here. RHS is the list of goals on the right-hand side of that clause and just push it into the stack and do what I have here. Pop a goal and repeat the algorithm from number one, push the goals to the top of the stack. Is there something simpler that we can do? Okay, so you are in fact jumping one step ahead. You are saying, what do we do with MGUs from all these sub-goals? Since now we have multiple sub-goals on the right. And in fact, all of them need to be merged, right? But you need to merge them sort of progressively as you go through these goals. Excellent. But even before we get to the business of MGUs, how do we change this code? Please. Right. Essentially, whether you use list comprehension or not, you are saying, we just need to iterate over these goals, doing exactly what we did before, but we do need some special handling for MGUs. So here is the only change, your algorithm we discussed, but here is the look what I have here. I just say, for all goals, I should say c.RHS just recurs. So it's a one-line change. But now we need to do something with those. Now we need to do something with the MGUs. And clearly we do need to do something with the MGUs on the way up. Do we need to do something with the MGUs on the way down? And this potentially exposes a problem in the first algorithm we have. So what we do in the first algorithm, we unify, create an MGU, we say things like x must equal to y. Okay, that's good.  And matching may happen quite nicely, successfully. But we are not propagating down the MGUs that we have built so far. So if up on the tree we have learned that x and y must be the same, we are currently not propagating it down. It could that be a problem? Also for the simpler case of one rule on the right-hand side, okay? I was, okay. So where did the propagation happen? So we are going back, we are going here, right? Oh, I see, I did. But I didn't use it here, okay? So what do we do with this MGU? Oh, okay. So exactly need to use it in unify, right? So that people understand why this is important. When matching these two terms you may discover that say x and y must be the same. Then when you do some other matching, the matching might succeed under the condition that x and y are unrelated. But if you additionally insist that x and y are the same, you could fail to find a match. Because you have now this additional constraint that can prevent you from matching things. Remember how we had the case where these two terms were not unifiable because we needed an infinitely many, infinitely large MGU? So there are cases where knowing more constraints would prevent unification. So we do need to pass this MGU down and use it in unify. I'll try to spell it out more nicely on the slide so that it is clear. And the same we need to do here, right? So we iterate over all of these just like before. We need to pass the MGU down, okay? But that MGU needs to do what? It needs to collect all MGUs from the rules so far, right? Indeed, for efficiency reasons, these MGUs are represented as tags that you add to them and then you pop from them when you need to backtrack. And this is exactly what we are going to do. So we'll get this, let's call it RMGU, the result from here, okay? Now we'll do MGU equals MGU, some sort of merge operator, RMGU. We merge them and now we'll pass it in here into this call, right? And now it looks like we are happy. Oh, I see. You could, but let's not go there. I think that this could be one of the optimizations, but I don't want to confuse things here, all right? So we essentially have done the MGU. Now, what will change here? I want to actually really quickly go through these algorithms because they are now really simple. In order to handle now these two choices, what do we change? We could loop through all of them, but let me give you a very simplifying assumption and that is all I care about is find one solution, right? Now, you don't know which of these matches leads to the solution, but an oracle would know. So imagine somebody knows which choice to make and they give you the choice, all right? How do you change the algorithm? By the way, read about the search treat may simplify your understanding of what is going on, but let's look at here. This is the algorithm that we had before. Here you match goals against the head, you produce the MGU, and now you have the problem of, well, what if there are multiple matches? And you need to intelligently pick from among them, so here we simply say oracle give me one, the one that is guaranteed to lead to an answer. That's the only change we need here, because if it gives us the right one, we are done, okay? This one here is essentially the same. You're asking the oracle, but you are keeping, you are looping over the rules on the right hand side, and now what happens here? If we don't have an oracle, how do we implement the oracle? If you understand that, you will be ready to do the final thing in here. So we cannot ask an oracle, what do we do? It is exactly what you said, iterate over them, okay? But is the iteration as simple as we think, okay? Is that sufficient? So essentially you're saying the structure is you have a recursion, and at each of our recursion you have multiple rules that you need to iterate through. You iterate all of them here, all of them here, all of them there. It's exponential because if you have 10 choices here, 10 here, 10 here, you have 10 to the depth of this chain. So indeed this stuff here is very simple. You just have a recursion plus loop at each level of the recursion. So why is this harder? Why do we ask for the use of coroutines there? So the answer is not that you don't have to go through all of them, you still have to go through all of them. But if you all of a sudden have multiple rules on the right-hand side, the simple structure that you just described, which is have a recursion, and each level of the recursion has inside a loop, it doesn't work. So try to take the algorithm that we have here, you can trivially extend it in here, you just ask an oracle. Here we added a loop to iterate over the choices at each level of recursion, and now the loop that we have here that handles multiple cases and the loop that we have here conflict, and you will find yourself needing coroutines to still be able to recurse nicely over the alternatives. So you'll go through it again in the recitation tomorrow, and you'll understand better why things get harder going from here to here. Thank you.


going to show you how to make one so you can play too. This is how you make a flower fairy. First you need a doll pin, then you're going to draw your doll's face. You can make your face however you want. I put on two eyes and nose and a smiley face. The next step is to make your skirt. We're using lots of leaves and flowers and petals. You can get these in your backyard or at a garden shop. Ask an adult to cut two holes through the middle of the flower so that these two ends of the doll pin can fit. Then you just slide it on. It's a skirt made out of flower petals.  I'm going to color my body orange. I'm making dots on mine. Beautiful! My body is done. And my body is done too. The next thing we're going to do is add fairy wings. We're using two fake leaves, but you can use real leaves if you want. To stick them on, use tape. I'm going to stick the wings on the back of my fairy. To do that, I'm closing tape in half so it will stick onto the leaves and to my fairy, my fairy. You can actually use anything you want to decorate. You can put on ribbons, you can put on tissue paper, you can put on fabric. Once you're done decorating, you're ready to play. I wish I had someone to go to the flower festival with me. Bounce, bounce, bounce, bounce. Hi, what's your name? I'm Lily the Bouncy Fairy. My name's Veronica. Hi, Veronica. Are you going to the flower festival today? Sure.


Germany could be involved in a war with Russia. Schultz opposes supplying Ukraine with Taurus missiles. German Chancellor Olaf Scholz once again opposes the supply of long-range Taurus missiles to Ukraine. In his opinion, this could involve his country in a war with Russia according to RND. We must, under no circumstances, be aligned with the objectives achieved by this system. Therefore, this is not the next item on the agenda. This clarity is also necessary. I am surprised that some people are not concerned at all. They don't even contemplate whether what we are doing might, in some sense, lead to participation in war, says Scholz. He explained that Taurus missiles are long-range weapons and what the English and the French do in terms of target control is impossible to do in Germany. Anyone who has dealt with this system knows this, adds the Chancellor. Scholz noted that he is very irritated by the lack of balance between what is really needed now and the discussion about Taurus. What Ukraine lacks is ammunition for all possible lengths and distances, but not fundamentally from Germany, he emphasized. Recall that Ukraine has been urging Germany to initiate the supply of long-range Taurus missiles capable of destroying targets up to 500 km away since last year. However, the German government refuses to transfer such weaponry. According to media reports, Chancellor Olaf Scholz himself opposes it. He is concerned that the Ukrainian armed forces could use German missiles to strike Russian territory, making Germany a party to the conflict. Iran transfers hundreds of 700 km range ballistic missiles to Russia. Iran allegedly provided Russian occupiers with around 400 ballistic missiles. They are capable of destroying targets up to 700 km away, according to Reuters. Three unnamed Iranian sources told the media outlet that part of the transferred missiles are from the Fateh 110 short-range ballistic missile family, including the Zolfagar. Such a missile is capable of destroying targets at distances ranging from 300 to 700 km. As one of the Iranian sources revealed, the deliveries began in early January after an agreement was reached at meetings between Iranian and Russian military and security service representatives at the end of last year. These meetings took place in Tehran and Moscow. Another unnamed Iranian military official clarified that there have already been at least four deliveries of missiles. A new transfer is expected next week. Another official stated that some of the missiles were sent to Russia by ship via the Caspian Sea while others were transported by plane. There will be more shipments. There is no reason to hide this. We are allowed to export weapons to any country that we wish to, he added. An American official informed Reuters that Washington has seen evidence of active negotiations between Russia and Iran, but there are no signs yet that the deliveries have taken place. Rumors that Russia wants to obtain Iranian ballistic missiles spread as early as last year. Ukrainian intelligence services are verifying information about a possible transfer by Iran of its ballistic missiles to Russia, stated Andrew Cheneyak, a representative of the Defense Intelligence of Ukraine in a comment to RBC Ukraine. Iran became the first country to supply weapons to Russia for the war with Ukraine. Thus, the Russian army consistently receives Shahad strike drones from Iran which are used to attack Ukrainian cities and infrastructure. In addition, Iran helped Russia set up its own production of these drones. Russia's Black Sea War Plan isn't working. UK. Russia's tactics against Ukraine's creative warfare in the Black Sea are falling short. According to a new assessment, as Moscow and Kiev step into the third year of all-out war. According to Newsweek, Russia can still strike at Ukraine from the eastern parts of the Black Sea, but it is increasingly evident that the defensive posture adopted to mitigate against Ukraine's non-conventional approach to maritime warfare is not working as intended. The British Defence Ministry said it is noted that shortly after Russia launched its full-scale invasion of Ukraine in February 2022, the Black Sea emerged as a key battleground between Kiev and Moscow. Ukraine has vowed to reclaim Crimea, which sits to the south of the mainland on the Black Sea but has been controlled by the Kremlin's forces since its annexation in 2014. Ukraine does not have a large navy but has made impressive use of naval drones to carry out dramatic strikes on Russia's Black Sea assets that have proved deeply embarrassing to Moscow. Russia's Black Sea operations have been greatly complicated if not paralysed by the nearly two years of all-out war between Moscow and Kiev, Ukraine's navy said in early February. Ukrainian-designed Magura V-5 naval drones attacked and destroyed Russia's Caesar-Kunikov large landing ship near the southern Crimean city of Alupka, southeast of Russia's naval base at Sevastopol, Ukraine's military intelligence agency said earlier this month. Russia has lost a slew of other vessels, including its Black Sea flagship, the Moskva, several other landing ships, and a submarine. Ukraine has used uncrewed vehicles and guided missiles to push Russian threat perception to new highs and force Moscow to shift many of its assets further east away from mainland Ukraine, the UK government evaluated. The Kremlin has relocated some of its Black Sea assets from the peninsula to its Novorossiysk base in Russia's Krasnodar region further from Ukraine's coastline. Russia is also thought to be establishing another Black Sea base in Abkhazia, a breakaway region internationally recognised as part of Georgia. This would move Russia's resources in the Black Sea even further away from Ukraine's reach.


Hey everybody, Matt here for Leighton Sports Cards, ripping 2021 Panini Flawless Football Hobby, one box break number 50, random left side serial numbers. Once again, there are the results of the random. We'll leave that up there for just a minute and then we'll rip this. First box in this case was decent, but I've got to think there's a huge hit coming in this one. That's MVP Aaron Judge, Mike. Here we go. Come on, monster. All right, first up, triple patches, 17 of 25, Tony Pollard, Tony Dorsett, Nazekiel Elliott, again, that is 17 of 25. 17 spot, Joseph R. Joe Montana, triple patch, three of five. Three spot is Phil K. Got a tag and two patches there, chiefs, chiefs Montana. Just like it should be. This is Otto, seven of 25, Nico Collins, seven spot is Matt S. This is dual tag with the shield and Nike Swoosh, Otto, two of three, Chris Godwin, two spot is James A. Awesome hit. Nice Godwin. Mag that one. This is rookie dual patch, Otto, 14 of 15, Ron Dale Moore, 14 spot is Dan M. That might be Jersey number, but it's not. From 2020, flawless, that is rookie patch, Otto, five of five, Clyde Edwards, Hilaire from 2020, flawless, five spot, that is Eddie C. There you go. That's a glove relic there. Yeah, chief spot. This is Cowboys. I guess it doesn't matter the team, but Dallas Cowboys quarterback, one of 15, Otto, Roger Stalbach, one spot is Ronald R. Honored Inc. Awesome hit. It was a glove relic, rips on the Clyde. Beautiful Stalbach. That inner box was loaded. Yeah, it was. Usually is when that encased hits aren't any good. Yeah, for sure. This is Ruby Jim, six of 20, Jalen Hertz, six spot, that is Marcus D. There's the diamond guarantee. Nice Hertz. This is Sapphire Jim, six of 15, Tom Brady, six spot, Marcus D again. Congrats, Marcus. Nice Brady. And last hit of the break, rookie patch, Otto book, Mac Jones, class of 2021, big hit. And that goes to the eight spot, eight of 10, Jason T. Congrats. Huge hit. That is awesome, man. Great way to close out flawless for tonight. Jeez. Awesome briefcase. That'll do it. Thank you, everybody. Appreciate it. We have Eminence coming up next.