1
00:00:04,024 --> 00:00:11,053
In this video, we're going to take a look
at Java Arrays. Let's say we have two

2
00:00:11,053 --> 00:00:16,097
classes, a and b, and that b is a sub
class of a. And let's think about what

3
00:00:16,097 --> 00:00:21,014
happens when we execute the following
piece of code. So, the first thing we're

4
00:00:21,014 --> 00:00:26,013
going to do is we're going to allocate an
array of b's. So, this is an array that's

5
00:00:26,013 --> 00:00:33,331
supposed to hold B's, okay? And, we're
going to have an array variable b here

6
00:00:33,525 --> 00:00:38,744
that points to it. And then, we're going
to have another variable, array variable

7
00:00:38,744 --> 00:00:44,581
A, that also points to the same array as
B. But notice the type of a. So a is an

8
00:00:44,581 --> 00:00:49,718
array of A's, little a here is an array of
A's, and b is typed as an array of B's.

9
00:00:49,718 --> 00:00:56,416
And now what we're going to do is we're
going to assign into a sub zero, okay,

10
00:00:56,416 --> 00:01:02,008
into the first position of a, a new a
object. And that should be fine, right?

11
00:01:02,008 --> 00:01:07,027
Because a is an array of A's and that
seems like that should work out alright.

12
00:01:07,027 --> 00:01:13,004
Alright, so here there will be an a
sitting in the first position. And then,

13
00:01:13,004 --> 00:01:20,014
we're going to access b sub zero which,
because A and B point to the same array,

14
00:01:20,014 --> 00:01:24,035
is the same element as a sub zero. And
we're going to call some method that is

15
00:01:24,035 --> 00:01:30,024
not declared in A. Now remember, B is a
sub-type of A, alright? So B has all the

16
00:01:30,024 --> 00:01:35,005
methods of A. A but B might have more
methods. And since this is an array of

17
00:01:35,005 --> 00:01:38,391
B's, we should be able to call all the B
methods on it and yet here, when we call

18
00:01:38,391 --> 00:01:43,399
some methods that's declared in B but not
in A, we are going to get a run-time error

19
00:01:43,399 --> 00:01:48,074
because the object stored in the array is
actually an A object at the first

20
00:01:48,074 --> 00:01:53,035
position. To understand what's going on in
this example, we have to take a look at

21
00:01:53,035 --> 00:01:57,051
the sub typing rules in Java. So, if we
use a subtype of A if B inherits from A,

22
00:01:57,051 --> 00:02:02,036
that's one case. So if B and B inherits
from A, then B is a subtype of A. And

23
00:02:02,036 --> 00:02:05,047
that's just like in Cool and, and most
other object oriented languages. And

24
00:02:05,047 --> 00:02:09,018
we're, we're very familiar with that from
our lectures in type checking. Further

25
00:02:09,018 --> 00:02:15,006
more, type, sub typing is transitive. So
if C is a subtype of B, and B is a subtype

26
00:02:15,006 --> 00:02:20,077
of A then C is also a subtype of A. Okay,
a nd that's also completely standard. But

27
00:02:20,077 --> 00:02:25,031
then there's this other rule that's not
quite standard or is definitely

28
00:02:25,031 --> 00:02:31,028
nonstandard. And that's that, an array of
B's is a sub-type of an array of A's if

29
00:02:31,028 --> 00:02:35,012
the element types are in a sub-type
relationship. So if B is a sub-type of A,

30
00:02:35,012 --> 00:02:38,078
then array of B is a sub-type of array of
A. And Cool doesn't have anything like

31
00:02:38,078 --> 00:02:42,055
that, Cool doesn't have arrays so it
wouldn't even have the opportunity to have

32
00:02:42,055 --> 00:02:47,002
something like that. But this is also not
the way it's done in other languages that

33
00:02:47,002 --> 00:02:52,829
have objects and sub-typing. So let's take
a look at our little example again and let

34
00:02:52,829 --> 00:02:57,864
me explain it in a slightly different way.
So, the issue here is that we have a, area

35
00:02:57,864 --> 00:03:02,094
of memory, and it actually doesn't matter
here. It's not essential that this be an

36
00:03:02,094 --> 00:03:07,052
array. What's important is that's an
updatable part of memory so that we have

37
00:03:07,052 --> 00:03:11,325
pointers to it. We have two pointers to
it, a and b and we can, they can both read

38
00:03:11,325 --> 00:03:15,073
and write this part of memory. So this
could be just a single cell, it doesn't

39
00:03:15,073 --> 00:03:20,023
have to be an array of multiple cells. But
what's important is that there is some

40
00:03:20,023 --> 00:03:25,665
memory location that both of these point
to, that they can both read and write,

41
00:03:25,665 --> 00:03:30,572
okay? And the trouble comes and by the
way, that there's a name that, that's

42
00:03:30,572 --> 00:03:37,657
called Aliasing, okay? So when you have
two names, two program names for the same

43
00:03:37,657 --> 00:03:43,898
part of memory that is called aliasing,
and here you know, we have the, the two

44
00:03:43,898 --> 00:03:49,268
arrays, A and B, that point to the same
area of memory, okay? Now, aliasing is

45
00:03:49,268 --> 00:03:55,526
very common in real programs since not bad
by itself but the problem in this example

46
00:03:55,526 --> 00:04:03,941
is that A and B have different types,
okay? And in general, if you have aliasing

47
00:04:03,941 --> 00:04:09,821
updatable references, okay? Meaning if two
names for the same location, that location

48
00:04:09,821 --> 00:04:12,844
is both readable and writable, so it can
be updated through the two names. And

49
00:04:12,844 --> 00:04:18,742
those two names have different types then
that is going to be unsound, okay? We're

50
00:04:18,742 --> 00:04:24,092
not going to have a sound type system and
to see the problem, let's say here in this

51
00:04:24,092 --> 00:04:32,476
case what was it? We had that B, type B
was sub type of A, okay? And what did that

52
00:04:32,476 --> 00:04:38,323
mean? Well that meant is we could do a
wright through this pointer, okay? And

53
00:04:38,323 --> 00:04:43,948
write an A object into this location and
then we could read that out through this

54
00:04:43,948 --> 00:04:50,608
point over here as a B object. But now, it
doesn't have all the methods and, and

55
00:04:50,608 --> 00:04:55,098
fields of A and treating it as the object,
we could potentially use an operation on

56
00:04:55,098 --> 00:04:59,280
it that's undefined. And you can see that
it doesn't help if we swap the roles of,

57
00:04:59,508 --> 00:05:04,647
of A and B, alright? So in particular, if
we reverse the, if we reverse the

58
00:05:04,647 --> 00:05:08,611
sub-typing relationship so that A was a
sub type of B, we can do exactly the same

59
00:05:08,611 --> 00:05:13,494
problem because aliasing is symmetric. We
just do the write through the B pointer

60
00:05:13,494 --> 00:05:17,843
and the read out of the A pointer swapping
the roles of the recent right here and we

61
00:05:17,843 --> 00:05:22,485
have exactly the same problem. So in
general, multiple aliases do updatable

62
00:05:22,485 --> 00:05:28,250
locations with different types is unsound,
okay? And this problem actually has come

63
00:05:28,250 --> 00:05:32,283
up in many different programming
languages. Java is not the only

64
00:05:32,283 --> 00:05:37,470
programming language to have had this
issue. It's a fairly subtle aspect of type

65
00:05:37,470 --> 00:05:42,608
systems and in many languages have done
things similar to Java where they've

66
00:05:42,793 --> 00:05:47,723
created a problem really for the static
type system by wanting to have a

67
00:05:47,723 --> 00:05:53,172
sub-typing work through arrays. Now, the
standard solution or the solution that's

68
00:05:53,172 --> 00:05:57,342
used in, I should say, in many languages
and is probably most widely accepted in

69
00:05:57,342 --> 00:06:01,652
the programming languages research
community is that you need a different

70
00:06:01,652 --> 00:06:07,484
sub-typing rule for arrays. So we would
say, you know, the rule that is commonly

71
00:06:07,484 --> 00:06:12,949
used the standard solution to this problem
at the type level is that to do the

72
00:06:12,949 --> 00:06:17,819
following things. So you only allows
sub-typing on arrays. So, you know, an

73
00:06:17,819 --> 00:06:23,437
array of B's is a sub-type in array of A's
only if B and A are the same type. If B =

74
00:06:23,437 --> 00:06:29,690
A. And if you think about that for a
second, if we have an array and now we

75
00:06:29,690 --> 00:06:35,578
have our two pointers to it, A and B and
we know the type of A the subtype or the

76
00:06:35,578 --> 00:06:40,681
type of B. Well, that only h appens if the
element types are, are equal. And so we

77
00:06:40,681 --> 00:06:45,624
can't create two references to an
updateable location with different types.

78
00:06:45,624 --> 00:06:51,021
Okay, and that will guarantee soundness
of, of the type, of the type system. So

79
00:06:51,021 --> 00:06:57,139
Java fixes the problem differently. So
instead of statically checking that array

80
00:06:57,139 --> 00:07:02,684
accesses will all be type correct, Java
does this at run time. And so whenever an

81
00:07:02,684 --> 00:07:07,548
assignment is done into an array at
runtime, Java checks whether the type of

82
00:07:07,548 --> 00:07:13,797
the object being assigned in compatible
with the type of the array. So when you

83
00:07:13,797 --> 00:07:19,498
say new B sub ten in Java, Java will
remember inside the array that this was

84
00:07:19,498 --> 00:07:23,231
supposed to be an array of Bs. And then
whatever you assign into the array, it

85
00:07:23,231 --> 00:07:27,774
will check that the thing you're assigning
is either a B or a sub type of B. Now,

86
00:07:27,774 --> 00:07:33,465
this obviously adds an overhead on array
computations so every assignment to an

87
00:07:33,465 --> 00:07:38,725
array is going to have, have a type check
on it at run time. And fortunately though,

88
00:07:38,725 --> 00:07:44,054
the most kinds of arrays are arrays of
primitive types, in particular arrays of

89
00:07:44,054 --> 00:07:48,054
ints and arrays of floating point numbers
and these are not affected because the

90
00:07:48,054 --> 00:07:52,471
primitive types are not classes. There's
no subtyping on them and so you can never

91
00:07:52,471 --> 00:07:57,184
create an array, say, of floating point
numbers, with any kind of subtyping

92
00:07:57,184 --> 00:08:01,855
relationship that would result in this
problem. So, so, that we're saved, or in

93
00:08:01,855 --> 00:08:06,771
better shape, for the primitive types, and
they don't need these extra checks. But if

94
00:08:06,771 --> 00:08:10,524
you have arrays of objects, then we do
assignments into those arrays in Java,

95
00:08:10,524 --> 00:08:14,071
there's additional run time overhead.