[MUSIC] This segment is about mutual recursion. It's a small topic that we just didn't need before, but, it would be a mistake to move on from ML without discussing it. Mutual recursion is just when you have two or more functions that need to call each other. So what if you wanted to have f call g sometimes and g call f sometimes? Now, is this useful? Yes, it's useful in a number of idioms and patterns that come up and we'll show a particular example in this segment where we're going to implement a little state machine but there's a problem. And that problem is that we've seen in ML that you have to introduce bindings in order, that the only functions in your environment are things that were defined earlier into the environment and yourself for recursion. So, how are we going to get f to call g and g to call f? Well, I'll show you two ways. The first way is ML does have special support for this and you should use that special support, because it's good style when you want mutual recursion. And second, I'll point out that we don't actually need the special support, there is a workaround with high order functions and it's just another example of using high order functions to accomplish something useful. So, here is the built-in support I just never showed you before. It turns out that if you have a bunch of function bindings in a row, and if for after the first one you use the word and instead of fun. So it's fun f1, and f1's definition, and f2, definition, and F3 and you can have as many of those as you want, then, this is all in some sense one bundle of mutually recursive functions They are all allowed to call each other. They are all added to the environment for all of the others and they're type checked and evaluated as, as one package if you will. So that is all we really need to have f call g and g call f, we just have to put them next to each other in our file and use the key word and. Now interestingly, we can also do this for data type findings, this is really a separate construct, but suppose you wanted to introduce two types that referred to each other, so one of the constructors of t1 holds a t2 and one of the constructors of t2 holds a t1. We also have not been able to do that before, and it's the same idea where we replace the keyword datatype with the keyword and. Okay? So that's the, it, kind of it for the language construct. Now, let's see this thing useful. The idiom I want to show you for using mutually recursive functions is just one of several things mutual recursion is useful for, is implementing a little state machine. Now, in case you've never seen a finite-state machine, it's a very important concept in computer science, I encourage you to learn about it. But the idea is that we want to process some input of unknown length, so some list of input that can have any size. And as we process it, we're always in one of a finite number of known states and we read the next level of the input and that tells us what state to go to next. And then when we're all done with the input, certain states are, true, yes, we accept, and certain states are false, no, we reject. That's the idea of a finite state machine, they come up all the time in computing. So the way we can implement a finite-state machine with mutually recursive functions is we just have one function for each state. So we could call those states state one, state two, and so on it, depends what kind of state machine we're implementing. They would all take the remaining input, they would all look at the first element of that input, and then they would just call whatever function represents the next state. So let me show an example of that, since I don't expect you got it from the slide. Here's a function, match, that takes in, in this case, an int list, and what it does, is it only accepts lists of ints that look like 1, 2, 1, 2 some number of times. So the empty list would actually pass, because it has 1, 2 zero times but, if it's anything other than a 1 or a 2, it's going to reject and otherwise, it's going to be 1, 2, 1, 2, 1, 2 and it has to end with a 2. So, all I'm going to do inside my body of match is call this helper function I defined s_need_one on the whole list. These are my two states, need_one is the state that says I better have a one next if I have anything and s_need_2 is I better have a two next if I have anything. So here is how it works, s_need_one looks at that list, if there's nothing left, then on before when I need a one, so that's true. I saw a two last or I started with the empty list. Otherwise, if I have a one first and I don't think I ever showed you, you can put integer constants in patterns, but that really is an orthogonal issue not particularly relevant here. then what I want to do is switch to state two with the rest of my list. Now, in general, for finite-state machines, I could have other possibilities where I have other states, but there's particularly simple example where I just have two states, I go back and forth between. And, any other case, I'm going to immediately reject and return false. S_need_two takes in the input list, if there's nothing more, it says false, because whenever I call s_need_2, I need another two because I just saw a one. If I have a two at the beginning of my list, then call s_need_one with the rest of the list. And so on, we go back and forth, if I see anything other than a two, I return false. Now, let me be honest with you this is not the simplest way to implement this particular function, but this is a particularly simple problem that can be answered with a finite-state machine. Anything, any function that processes a list of say integers or strings or whatever by looking at one element of it at a time, and moving between things that don't need to keep track of any more state than a finite number of possibilities can be implemented in exactly this way. You could actually even automatically take a description of a finite state machine and translate it down into a collection of mutually recursive functions. So I thought I would show you that idiom as a general phenomenon in computing. Alright, let's do a second example. This example is going to be silly just to keep it short. [COUGH] But what I have here is a mutually recursive datatype binding. So type t1 is either a Foo of int or Bar of t2 and data type t2, I really am defining two datatypes here, is either a Baz of String or a Quux of t1. So each of these datatypes refer to the other one. Alright? Now, suppose I wanted to write a function that took either a t1 or a t2, these will be different functions, and made sure that there were no zeros anywhere in it and no empty strings anywhere in it. Okay? So, here is how I would do it. I would write a function no_zeros_or_empty_strings_t1 that took in an x. If it's made out of the Foo constructor, I need to make sure i <> 0. If it's made out of the Bar constructor, then what I have here in y is a t2. So I want to call this other function I wrote for no_zeros_or_empty_strings_t2 with that argument y. And here is that other function, I've made these two mutually recursive because that other function, well, if x is a Baz, then just make sure it's not empty, its size is greater than zero. But if it's a Quux, then I want to call the first function I wrote. So there is no good order here. I really do need them to be mutually recursive. Okay? So that works, that's fine, it's not a particularly interesting example. thought I would use this example to show you a different work around. So a work around if you did not want to necessarily put these next to each other or if you were in some setting for some reason that you really could not use mutual recursion. So the idea is to use our old friend, the higher-order function and have one of these functions take in the other one as an argument. So here, what I've done is I've written a version where they are not mutually recursive, so this thing takes a t2 and make sure that it doesn't have any zeros or empty strings. So the Baz case is still the same, make sure you don't have the empty string. For the other case, I want to call this function up here. Now, this function up here is not going to be able to call this function directly, because it's not in its environment, but I could still pass it as an extra argument. So what I've done is I've made my function over t1 take not just an element of type t1, but also take a function, this function f happens to have type t2 -> bool, Alright? So I could pass in any t2 -> bool, but the one I'm going to pass in right here is the function I want to call. So one way you can get an earlier function in your file to call a later one is to pass it as an argument, and once we can do that, everything works out just fine and this is an equivalent solution to the one that used the built-in support for mutual recursion. By the way, this is a slower implementation, the built-in support will implement this in a much more direct and efficient way, but I just thought I would show you this as a technique and flip back to the slides quickly to show you in general what we do. That if you want to have some earlier function, call a later function, change your earlier function to take in an extra argument f, and then, when you call the earlier function, pass in, I'm sorry not f here. I'll fix this after I finish the recording, pass in later, right? So call earlier with later and y and everything will work out correctly. And that's really everything I have to tell you about mutual recursion.