0:00

[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.