[MUSIC] This segment is going to introduce an example that we are going to use for the rest of our study of module systems. So we'll get very used to it and it's worth going through the code before we get started. The example is going to implement an abstract data type. It's just a module that exports some new type of data and some operations on it. And for a simple example that doesn't take too long to implement, I've a little library for rational numbers. So these are numbers that can have a numerator and a denominator where both the numerator and the denominator are integers. And the operations I'm going to support are making these things, these fractions if you will. Adding two of them together and then converting them to a string. So for example, if you had number three halves, would turn out three slash two when you convert it to a string. So I'll show you the code in just a second, let me give you a high level picture of it. I'm going to have a structure named Rational1, because in later segments I'm going to define rational two and rational three. I'm going to have little data type for my rational numbers that has either the constructor Whole, for whole numbers, carries one int, or Frac for fractions, that carries two ints. I've got an exception BadFrac in case someone tries to make a fraction with a denominator of zero because I want those to be undefined in the raise an exception. And the function make_frac that takes in a numerator and a denominator and returns a rational. Add for adding two rationals and toString for taking a rational and returning a string. Now the implementation of my module is going to have local helper functions, that I'll show what those do in just a second. And in the next segment, when we give this structure a signature, it will not surprise you that we will choose to hide those. So the outside world doesn't have to rely on them. So next, let's go over and show you the code. So here it is. It has the datatype definition, just like I promised you and the exception, just like I promised you. And as we're going to talk about more in a minute, the implementation of this module is going to keep a couple in variants because it's going to promise a few things. What I didn't tell you yet about this module is that I'm going to make sure that we always return strings that are in reduced form. So we would never return the string nine slash six. We would instead return three slash two. And we wouldn't return the string eight slash two, we would return the string four. So we're going to do that by having a couple helper functions. The key helper function is this one reduce. Reduce takes in a rational and returns a rational and what it does is it return something in reduced form. So if it starts with a whole number, just return the whole number. Those are always reduced. Otherwise, if it's a fraction of an x and y, if x=0, the numerator is 0, then the whole thing is 0, right. Zero over anything should be zero. Remember we're not going to allow zero denominators. Otherwise, it turns out what we need to do is compute the greatest common divisor of x and y, but my gcd function assumes that x and y are positive. So I'm going to (abs x, y), my denominators will always be positive, that's another invariant that this module is going to enforce. Then if d, the greatest common divisor, divides y, then we should be a whole number, x div d. Otherwise, we should div the Frac(x div d, y div d). And I will leave it to you to either trust me or check me on the arithmetic that this does reduce a fraction to reduced form as long as gcd is implemented correctly. I have that right up here. This is another algorithm that I will not convince you is correct but if x and y are greater than zero, this will do the right thing. And believe it or not this is a recursive algorithm that is over 2000 years old. It goes back to ancient Greece I believe. And so humankind is fairly convinced that this algorithm is correct. So that's kind of neat. These are just helper functions. Now let's talk about the functions that our clients are going to use. I have make_frac which is going to take in an x and a y, if y=0, you're trying to grade a fraction with a zero denominator, I'll raise an exception. If y < 0, I don't want negative denominators, that's one of the invariance this model is going to maintain, so instead I'm going to return Frac(-x,-y) so that's going to make y positive. And x will have the opposite sign of whatever it did when it was passed in. And then I need to reduce that, because maybe you call make_frac with 9 and 6 or 9 and negative 6. And then I want to return negative three over two, okay. Otherwise y is positive so we'll just reduce(Frac(x, y). So now we've created fractions that are in reduced form. If we want to add the two together, we're going to assume they're in reduced form and make sure the result is in reduced form. This is a great example for nested pattern matching. If you have two whole numbers, return the whole number that's the sum of those two numbers. If you have a whole number and a fraction, it turns out if that fraction is already in reduced form, then so will be the result of adding a whole number. So we can just return j+k*i,k. If you have two fractions, then we can compute a new fraction as a*d + b*c, b*d. But then we need to reduce the result and again this is a primary school arithmetic but I know I am always a little forgetful on these things. It's okay if the exact arithmetic is a little surprising to you. It's not really the point of studying module systems. Okay. And then finally we have this thing that prints out the string. Now this is very interesting. Because we keep all our rationals in reduced form, we can just go ahead and print it. So if it's a whole number, just convert it to a string. Excuse me, we're not actually printing here, we're just converting to strings but then the REPL prints out our results, so that's why I keep saying printing. And if you have a fraction then just (Int.toString a) concatenate that with a slash and (Int.toStrig b). So let me show you an example of using all of this. [SOUND] And then we'll talk a little bit more about the structure of our module. So there we go, I've defined my whole module and now I could say val x = Rational1.make_frac(9,6). All right and how about val y = Rational1.make_frac(-8,-2). And I'm just misspelled Rational1 in here. And misspelled make_frac. [SOUND] Okay, there we go. Now we could say Rational1.add(x, y). And I could just immediately have a Rational1.toString of that. [SOUND] And I get 11/2, which is in fact three-halves plus 4, which is the reduced form of nine over six and negative 8 over negative 2. So this is how I would use the module as a client. So, that's the idea. We see the structure here. We define our data type, our exception and these public functions make_frac, add and toString. Now I want to talk more about how abstract data types are typically implemented with modules. And I want to focus on the specification of the library in terms of properties and how it's implemented in terms of invariants. So what I'm calling properties are externally visible guarantees. Things that the library writer is promising any clients of the library. Some of the things that this module that I just showed you is promising, are the following. We will disallow any denominators of 0. If you go to make such a fraction, we will raise an exception. You will never see a rational with a denominator of zero. That all the strings we return are in reduced form. Well you see 4, not 4/1 and 3/2 not 9/6. And that except for disallowing denominators of zero any time you call a function it will terminate, it won't raise an exception, it always produces the correct answer. So there are additional properties, this is not a full specification but these are particular things I want to emphasize that I'm going to say our library must do, even though it's not in the types of the functions we're providing like add and to string. Now that's all the outside world should care about. Internally, our implementation is maintaining some important invariants. And what this means is that all of the functions are going to have to guarantee these extra things or other functions might do the wrong thing. Now the outside world should not care about this. These are implementation details but they're things that are across the module so that one function can rely on another function doing it correctly. So the first thing we're going to require is in fact that all denominators are positive. So the outside world can make a fraction with negative 8 and negative 2, but we'll return the fraction that doesn't have a negative denominator, okay. And so all of our functions can assume that. Second thing that's internal invariant is that, all of the rational values are already reduced. So we never even create a 9/6, we immediately create a 3/2. So let me emphasize that our functions are maintaining these invariants and relying on them in several places. So if you look back at the code, you'll see a number of things. So you see that make_frac, when we get started and we build a rational number, explicitly disallows a 0. It had a special case to remove a negative denominator, it immediately negated both the numerator and the denominator. And it called reduce on the result to make sure that we created a rational in reduced form. Then our add function assume that the two arguments were in reduced form. And it actually used that to avoid calling reduced in some cases where it did not need to. But in other cases, to be careful and to make sure it preserves the invariants, it did call reduce, okay. We're relying on these invariants and several other places as well. The gcd function is not correct for negative arguments and there are certain places where we called gcd with arguments that we only know are non negative. Because all of our module is maintaining this invariant. And similarly, in toString, remember toString, we promised the outside world would always return things in reduced form. But toString didn't check for that and did not call reduce, because it's relying on the invariant in the rest of the module. So that's our example and now what we want to do is use signatures to make sure that this properties and invariants cannot be violated by clients.