[MUSIC] In this segment, I'm going to show you a third
implementation of rational numbers that will be equivalent to our other two, as
long as we keep the type abstract. And what I'm going to do here, is
actually change the implementation of the type rational,
in order to emphasize that when the type is abstract, an equivalent structure can
go ahead and change how the type is implemented.
So, given a signature that has an abstract type, different structures can
have that signature while implementing the type in different ways.
Those structures might or might, might not be equivalent.
I'll show you an example where they are. So I'm about to show you a third
implementation, rational 3 And in rational 3, the type rational is going to
be implemented as a type synonym with int * int.
So let's go over and see that. Here is my structure.
You'll see I have a type synonym here, so in the rest of this module, rational and
int * int are the same type. The outside world, however, doesn't have
to know that. So before I show you these functions, how
about I just show you, remind you, what the three signatures look like?
Now signature RATIONAL_A requires the module to implement rational as this data
type. Since our module does not, rational 3
does not have this signature. If we try to give it this signature, the
type checker will reject it. But it does have this second signature,
RATIONAL_B. As we'll see, we already saw it defines a
type rational. It defines it to equal int * int. That's a fine way to implement a
type rational. But, given that definition, it's going to
have to have these three functions, where rational is int * int.
The outside world, as usual, will not know that rational is int * int,
and then for RATIONAL_C it can have this signature, provided it has everything it
had before, as well as a function of type int arrow rational.
And I'll show you that at the end. So, let's see how struct rational 3 is
implemented and the fact that it can have type, the signature RATIONAL_B.
So rationals are now just pairs of ints, in all cases.
So here's make_frac. If the denominator is 0, raise an
exception. If y less than 0, then produce (-x,-y).
Just like before, but now it's just a pair of ints, there's no frac constructor
involved. Otherwise return (x,y).
Notice we're not treating whole numbers any differently.
So if this denominator is 1, then we'll just, return (x,y).
Okay? To add 2 fractions, well, add needs to
take 2 rationals. And each rational is an int * int, so
this pattern will do well. And, we're not going to reduce things.
That's an orthogonal choice, but like Rational2, we're just going to wait until
toString to reduce things. So we'll just return a*d + c*b in the
first position, and b*d in the second position.
And then finally, toString is a little more complicated, because we still want
to return everything in reduced form and treat whole numbers specially here.
So here's what you need to do, if x is 0, you have a numerator of 0, you better
return the string 0. Otherwise We have some more work to do
here with GCD and reduce. so here's a let fun gcd equal this in,
let's convert to a string the numerator concatenated with if the denominator is
one then don't do anything. Else, a slash, and then to string of the
denominator. So, I didn't empahasize this.
Up here, I've computed the num and the denominator, by dividing both by the gcd,
of the absolute value of x and y. So, a bunch of arithmetic, but the point
is, to not print the denominator, if the, if the numerator is 0, or if the
denominator is 1. And so overall, if we go back up here to
the signature RATIONAL_B, we've provided everything at the right type,
make_frac returned an int * int, add took two int * ints and returned an
int * int. And toString took and int * int and
returned a string. And then the outside world does not know
that rational is int star int. Now, if we want to implement Rational3,
we also need a function, of type int arrow rational.
This was this cute thing where, for our other structures, the data type binding
was providing this function, and then we are exposing just that part of the data
type binding to the outside world. Now, in our new structure we don't have a
data type binding, we don't have such a function being defined by it,
but we can still implement this signature provided we have this function.
And so, again, it's a little cute, but down here at the bottom, I just defined a
function whole, you're allowed to start functions with a capital letter if you
want to, that just takes in an i and returns this
rational, this int * int of (i,1), and it works great.
So, that is our third implementation. I want to emphasize, that when we do
signature matching of this structure, against either RATIONAL_B or RATIONAL_C,
a couple of interesting things are going on.
So let me emphasize those for you. the first is make_frac internally has
type int * int arrow int * int. And so that does match a signature where
we're exploding, exporting it as int * int arrow rational, because rational is
int * int. And the client will never be able to tell
that we're actually returning something of the same type we're taking in, because
the client doesn't know those are the same types.
Now what's interesting, is we could If we went back here to RATIONAL_B, we could
say that make_frac, instead of being int*int arrow rational, it's actually
rational arrow rational. Now this is a very bad signature. The
structure has this signature. The type checker will accept it.
But, the structure will be useless. Because if all the outside world knows is
that it can use these bindings, it's never going to be able to call make_frac,
add or toString, because it can never get its first rational to get started.
There's no way it can call any of these functions.
So there are programs out there that type check and are not useful.
Okay? So we really want to expose here that make_frac does take 2 ints as
arguments. So that's the first interesting thing.
The second interesting thing is this function, whole.
So let me go back and show that to you here at the bottom.
Based on what we know from type inference, this is going to have type
alpha arrow alpha * int. And that is indeed what the type checker
will give this function internally, when it goes to type check it.
But in our signature in RATIONAL_C, we said this had to have type int arrow
rational. And so somehow, the type checker, which
is fairly sophisticated and fairly smart, has to get from this first type to this
second type legally, and it turns out it can, because the rules of signature
matching let you take a polymorphic function and instantiate it to a
non-polymorphic function. So the first thing the type checker has
to figure out to do, for signature matching, is to realize that alpha can be
int, and therefore, this could also have typed the less flexible type, int arrow
int * int. We have to replace all the alphas
consistently, and now we see, that indeed, since rational inside the module
is int * int, we can, as we usually do, match this type against this type in the
signature, and its pretty neat that ML does that for us.
Notice that this does not have something like the type, alpha arrow int * int, or
you know, int arrow alpha * int. When you take a generic type, a
polymorphic type and make it less general, you have to replace all the
alphas with another type. The, this function hold does not have
these bottom two types, that doesn't make any sense.
It is not the case, that if you called whole with a string, you would get back
an int * int, so these types are just wrong and I will delete them.
It is interesting to me that inside this module, we actually could call whole with
a string for i, but outside the module, because of what the signature says, we
can only call it with an int, and therefore it will return irrational.
Okay? So, that is the more sophisticated and interesting details of this third
structure. But the high level point is that under
RATIONAL_B or RATIONAL_C, this structure is equivalent to our other two
structures, even though it implements the type
rational and in, and in an entirely different way.
Dan GrossmanProfessor
