[SOUND] Okay. In this segment, we're going to start studying functions, these are new kind of binding. So we're going to change our program. definition of program will not just be a sequence of variable bindings but who are both variables and functions. If you haven't heard of the term function, it's a lot like a method in an object-oriented language. This is something that's going to take arguments, compute some result, and return that result. That's all it does so it's in many ways simpler than a method. And we're always going to call these things functions. So why don't I just flip over to Emacs here and show you a first example. How about I'll write a little function for exponentiation or raising something to the power of something else. So, here is most of what I need to write. Okay, so I have the keyword fun. The name of the function I'm defining, pow. The arguments it takes. Here X and Y separated by commas. I've written their types with a colon and then the type name. Then an equals. And then I have my function body. Okay, so that body can just be any expression I want and what happens when you call the function? It is, we are going to evaluate that expression and then the result will be the result of the function. So for exponentiation what I want is something like a conditional expression that says if y is zero, than one. Otherwise how about x times? this other expression which is to call the pow function with x and y minus one and that will work as long as y is greater than or equal to zero and I'll make no attempt to be correct for negative y since this is just an example. So, this is a program. this can be included in my sequence of bindings. I could have a val binding before. maybe afterwards, I could have another function binding. How about something that takes its argument and cubes it? So I could define this as x * x * x or I could use any previous bindings, since it'll be in my environment and I could instead, implement this as pow x3. So the body of this cube function is itself a function call that calls pow with x which is the argument to cube, and the constant three, alright? So, I could use these functions. I could say val 64. That should just equal cube of four. You don't actually need these parentheses but it looks a little more like other languages if I put them in, at least, for now or I could have something that uses you know more nested expressions like, you can call a function with an expression. In which case, I'll evaluate this 2 + 2 to 4 and then pass four as the second argument to pow. here I could add another sixteen, and another eight, and another two. You could even have nested calls if you wanted, so you could say, pal 2 comma 2 in there and so on. Alright, when you want to test something out, just like always, go over here to the repple. You can say, use functions.SML. See all of our bindings there. You'll notice that pow and cube print differently than variable bindings. In terms of the value, they just say, I'm a function. We don't print out the body of the function or anything, the reple always just say, here is a function. And here is it's type. So you see with pow, that it has type int star int arrow int. So the way function types are written in ML. As we write down the types of the arguments, separated by a star. So it takes two int arguments, int star int. And then a hyphenate angle bracket, an arrow. And then the result type, which is an int. Notice we didn't have to write down that result type. ML figured it out by looking at the function body. That conditional that we had up here and realizing that if x and y have type int, the conditional has the type, have type int. And so the function, when called, with two ints, will return an int. Similary cube is a function that takes one int and returns one int. 64 and 42 as usual, and we can you know try things out at the repel now. So we could cube seven and we'll get 343 and so on. So, that's the informal idea of functions, let me make a few points here back with the slides, since this is a new thing we're learning the first thing is that the body of the pow function, itself can use pow. So that's how we implement recursive algorithms, as we did here, so all this is showing is that inside a function body, you can call the function itself. There's a few gotchas when you start writing things out, we have all new sources of potential error messages. Especially if you leave that colon off between the name of the variable and the type or if like in other languages you try to write ent x instead of x colon int. All of these things are syntax errors and you're going to get error messages as a result. I would also point out that when we wrote out those function types in the repel, we saw that pow had type int star int arrow int. That star is different than the star for multiplication. So it's just a reuse of the same character. In expressions, star means multiply, in types, at least as we've seen so far, it's just separating the types of multiple arguments. And finally, just like variable bindings. function binding can use earlier bindings in the file. But they can't use later bindings in the file. And that's, again, just ML's rule. so any helper functions you want, if you want to define one function like cubed, in terms of another function like pow, then you have to put cubed second. Now, this does raise an interesting question. What if you had two or three functions that all wanted to call each other. There would be no good order to put them in. And I'll show you, in some future segments, some special support in ML for that case of mutual recursion. if you're not yet comfortable with recursion, hopefully you've at least seen it before. you will be soon on your first homework assignment pretty much every function you write will be recursive and we're going to see a bunch more examples. So, don't panic if the algorithm for pow looked a little too magical, but there's really absolutely nothing magical to it. So let me flip back here and just show you this pow function. The reason why we can define pow in terms of pow, there's nothing circular here. What we did is we defined raising something to the y-th power, in terms of raising something to the y - 1-th power. And that, is a perfect reasonable definition. A recursive call is solving a simpler problem and if that simpler problem is that y is zero, then we don't use recursion at all, and we just return the answer one. So we'll get very comfortable with this idea as we move forward. and in ML we're always going to use recursion for these sorts of things. If you're used to writing things like pow with while loops or for loops we're not going to use them. they often obscure what are simple, more elegant algorithms and recursion is more powerful. So, often while loops and for loops are more convenient or the idiom in many programming languages and many programming languages, they're more efficient. But anything you can do with a loop, I promise you, you can do with recursion. And we're going to focus on that approach in ML and most of the programming we do in the class.
