0:00

[MUSIC] It's now time to take our module example from the previous segment and

figure our a good signature to give it. And I think this will be much more

interesting than you might imagine. So from what we know so far, what would

be natural is defined as signature like you see on the slide that hides the two

helper functions that we don't want the outside world to know about.

So we make no mention of GCD and reduce, but the outside world does need to know

there's a type rational that can be wholes or fracs, that there's an

exception bad frac, there's a make frac that takes a numerator and a denominator

and returns a rational. Add takes 2 rationals, returns a rational

and to string takes a rational and returns a string.

And this signature is something we can give to our structure.

It will type check and then the outside world will not be able to use GCD or

reduced directly. So, that's okay.

It's not a bad start. But it turns out we made a crucial error.

And that is, that by revealing the data type definition, this first line here

where we told the outside world how rational was implemented clients can

violate all of our invariants and they'll be able to use the library in the way

that will not lead to the results and the behavior that we want.

Now we could include a comment, or we could ask clients to please, please

promise not to build their own rationals. To always call make frac, because make

frac checks for certain things, and insta, institutes our invariants when we

get started. But I don't know about you, I have

certainly found that when I put things in comments and documentation, my library

clients don't always follow those rules. And it would be much better if my

language had a way to enforce those rules.

And it does, and I'll show that to you in just a second.

But first, let me emphasize what goes wrong here under this first signature

rational A. The key problem is that clients will be

able to call the frac constructor directly.

They could make a frac out of an 1 and 0 or a 3 and -2, or 9 and 6 and these are

all forms of values that the functions in my library assume do not exist and once

they do exist, all sorts of things could end up going wrong.

So let me show some slightly different examples I've already included everything

here exactly as you've seen it, so I have this structure rational 1 that has the

signature you see right here, okay? And now let me just write some

things that work and some things that don't work.

So suppose I wanted to add 2 rationals and suppose first I do this correctly and

I call make frac. So 1,0 and make_frac of say two-thirds,

okay? If I do this, I get the exception bad frac which is the correct behavior.

But if my client does not follow the rules and makes a frac directly then it

goes in an infinite loop it turns out and we could try to figure out why I think

it's related to GCD. But we don't want to figure this out, we

want to keep clients from doing something like this.

Like this, alright. here's something else they might do if I

just had negative denominator I think I end up overflowing.

Again because the arithmetic just assumed in the module there wouldn't be a

negative denominator and if there is certain things are not behaving correctly

and as a final even simpler example. Remember, one of the things we promised

clients is that we would always print everything in reduced form.

But if they just called to string with a frac directly, we're just going to get

nine slash six. Because you may recall that our to string

code which you see here assumes its argument was already reduced.

And this is again something our client is able to violate,

okay? So this is what we want to try to prevent, and here's the intuition.

The intuition is that an ADT should hide the concrete representation of a type.

That way clients will never be able to make anything of the type without going

through our functions like make frac. That way we can get those invariants

installed and then out functions can keep them, so here's how you might think to do

this. Let's just take the signature we had

before and take out the data type definition don't tell clients that it can

be built from a whole constructor or a frac constructor.

So this does not work here, and the reason is the type checker sees

these types rational and says I've never heard of such a thing,

right? It'll just give an error and says, you,

you can't, you can't just make up type names like that.

I need to know there's a type rational otherwise I, I think you just, you know,

had a typo. Alright,

so that's good the type checker is helping us.

Somehow what we want to do is tell the type checker, that for this signature,

yes, rational is a type. But no, I don't want clients to know

anything more about it. And that is an absolutely crucial idea,

which is known as an abstract type. You can know the type is exists, but you

cant know it's definition. So this is how we do this in ML, this is

a feature provided by ML, which is in signatures you can just write type and

the name of a type. And if you have no equals and no more

information, it means what I just said. The type exists, but the outside world

can't know what it is. So here is a signature I like very much.

I'll call it rational B, and it tells clients what they can know

about rational. It says you can know there's a type

rational. You can know there's an exception

BadFrac. You can know that make_frac returns a

rational given 2 int's. Add can take 2 rationals and return a

rational to string can take a rational and return a string.

And if we gave Rational1 this signature, we will still be able to try all the

examples that use make_frac correctly, but the outside world no longer knows

there is a frac constructor. Capital FRAC, and so it won't be able to

create any of those vowels that violate our invariance.

So this is a really big deal, there is nothing a client can do not to violate

our invariance. We could take the structure we studied

carefully in the previous segment and this signature and convince ourselves

that all of our properties will always hold, here is the intuition of the

argument. How we will make it rational?

The first rational acclaim ever makes has to be made make_frac, because this is all

they have to create rationals, you can't call add until you have a rational.

You can't call to string until you have a rational.

So, you're going to have to start with make_frac.

We could study the code for make_frac and convince ourselves that it gets all the

invariants and properties correctly, no zero denominator, no negative denominator

fraction in reduced form. After that, the only thing you can do

with rationals is add them together and convert them to strings and we would

similarly convince ourselves that those functions were implemented correctly.

Now to the outside world it can do what it wants with the rational values it can

put them in lists, it can pass them to functions it can put them in tuples, but

the only operations it can perform that access the pieces Are those provided in

our library. Now, the reason why our structure

actually has this signature, is because it does define everything.

Defines make_frac added to string and can have these types and it does define a

type rational. It does it with a data type binding, that

is a perfect good way to define a type. The outside world just doesn't know you

did it with a data type binding, and it certainly doesn't know that details of

data type binding. And this is how you use signatures of abstract types to

properly enforce obstructions and implement abstract data types.

So, what we have now are two powerful ways to use a signature to hide things

from clients. The first one is to deny bindings exist.

That if you leave val-bindings, fun-bindings, constructors and so on out

of your signature, they simply don't exist to clients.

But, the second more sophisticated and more exciting way to hide things, is to

take a type definition. Tell the outside world that yes you have

defined this type, but I'm not going to tell you how I did it, and that's

important, so that we can say that make frac.

Returns a rational and takes 2 rationals and returns a rational without revealing

what the rational actually is. We'll see some other things that

signatures can hide in, in, one of the later segments on modules but these are

the 2 things I hope you'll always remember.

Now before we finish up this segment, I want to show you a third signature that's

also in the code file that's posted with these materials and this is just a little

bit cute. So it turns out that if you look at the

data type binding for this module which I have right here, It was a problem for our

invariance, to export the frac constructor, and I showed you a bunch of

examples of that. But it turns out, it would be fine, to

export the whole constructor. That our library doesn't mind, any int,

past the whole. So you cant get in trouble that, that's,

has to do with our particular properties in invariance, but it turns out you can

convince yourself it would be okay, if clients used whole directly, okay? So we

actually can export it and we can do it with this signature.

It turns out we could go ahead and tell clients that there is a function whole

with a capital W of type int arrow rational.

And if you take this structure as we've already defined it and type check it

against this signature, ML allows it. And that's kind of surprising perhaps,

but the reason why is when it sees this data type binding, it remembers all the

way back from when we first learned data types.

That this defines a number of things. It defines a type rational yes, but also

a function whole of type int or a rational, Frac of int*int, a rational, as

well as Whole and Frac being allowed to be used in patterns.

Signatures let us hide some things and reveal some things.

And in this particular example, ML will allow us to expose that there is a

function Whole of type int rational. There is a type rational, but still hide

all the other things that data type binding gave us.

This is a bit of a peculuraity to ML, I don't think this is the most important

feature in a language, but I do find it cute and I find it, that it emphasizes

that signatures get to expose some things and hide other things.

And there's just a particular way we could let clients do a little bit more.

They can call Whole directly rather than having to call make_frac with a second

argument of int.