Motivation for Value vs. Reference Semantics
Why do we have different behaviour for different types?
Memory is made up of so-called words which are blocks of memory of a certain size. Most computers have 32 bit or 64 bit blocks which is convenient as they will fit all primitive types inside of them. We can hence easily store any primitive type variables directly in memory. Memory however has a limited size so we need to be careful not to waste memory. A reference or address to a memory location describes its location and in most systems this reference is 64 bits wide. It thus makes sense to store all primitive types directly into these variables instead of having a reference of the same size telling us where in memory we will find the value we are looking for.
A large file, an image and other information and data will not fit inside a 64 bit variable and might be much larger. Hence we want to avoid copying this data at all cost. This is why a variable cannot contain the data directly and instead stores the address in memory of the data, which we call a reference to the data. This is the reason why we distinguish between value semantics and reference semantics, not because we chose to, but because we have to.
Value Semantics
Definition
All primitive types follow value semantics, this is because they use at most 64 bits and thus every variable (on a 64 bit system) can carry a copy of the value of the variable directly. Hence a variable always contains a copy of the data. This tells us that writing to variable of primitive type only affects this copy of the data. One must remember this when working with primitive types.
The code to the left will, when the main method is executed, print 0 twice. This is because the parameter of the method changeValue is of primitive type and thus only contains a copy of the value. The statement a = 2 only has an effect on this local copy of the variable.
This is an example for when two variables with the same name exist but they are not connected to each other. It is important to remember that simply looking at names of variables does not tell us if two variables are the same. This behaviour will be tested in many exercises and you should really understand how value semantics work. To be able to understand this reading an explanation is not enough. You need to practice and implement such examples yourself to verify whether you understand the concepts or not.
Reference Semantics
Definition
We have discussed Java objects briefly in the introduction to Java. Everything that is not of primitive type has a class associated to it and one can create objects of it. All of these follow reference semantics. This means that a variable of an object contains a reference to the actual data in memory. Changes made using this reference will have an effect to the underlying data besides if changes are not allowed.
Distinguishing this behaviour is important and you need to treat Java objects different from primitive type variables. A parameter of a method will not contain a copy of an Object and instead a reference to the actual data, hence changes in methods will have an effect. Whenever you forget this your program will do interesting things so whenever you pass as a parameter to a method verify that anything you do does only change data if you want it to do that.
Creating copies of objects is possible but one must manually create a copy by calling a corresponding method.
Immutable Types
What about Strings?
People often argue that there is not such thing as there only existing value semantics and reference semantics because "Strings are objects but they act according to value semantics.". This is wrong. Strings are objects and they follow reference semantics. They just are special objects. They are immutable objects. Immutable objects cannot be written to once they have been created. They are still passed by reference to a function.
One can also call methods on a Strings which is only possible on Objects. Understanding this is very important as this often causes confusion. Once you understand well how value and reference semantics work you will be able to fully understand what your code does. The Java documentation says the following referring to Immutable Objects:
"An object is considered immutable if its state cannot change after it is constructed. Maximum reliance on immutable objects is widely accepted as a sound strategy for creating simple, reliable code."
One might now ask how we can still change Strings if they are immutable. This is because a variable containing a reference to a String contains only its reference. If we assign another String to it, then a new String object is created and we store a reference to this new String object inside our variable. The reference to the old String is lost in the process.
Loops
for Loop I
Up until now we have seen many of the control forms from EBNF translate to Java. This includes option in the form of if / else statement, sequence with number, Strings and other types, recursion with its counterpart in Java. We are missing repetition however. We will now introduce loops which allow us to do repetition in Java.
A for loop has a head and a body similarly to if / else statements which contain the condition in the head and statements in the body. A for loop comes with three statements in the head and a block of statements to be repeated in the loop body.
We have the loop initialisation which is the first statement to be executed when entering the loop, this could be initialising a counting variable for example. The second statement is the termination condition which is tested before every loop body execution, if the condition holds then we execute the statements in the loop body once again. The update statement is a statement that is executed after every loop body execution and could for example increase / decrease a loop counting variable.
Loops
for Loop II
In a for loop you may add all three statements in the header or leave out any you do not want to use, i.e. the statements in the head are optional. If all statement are removed then the loop with execute its body forever. Most of the time all three statements will be used. The most likely statement to be removed is the initialisation statement.
We can also have for loops inside of each other which we call nested loops. Nested for loops are often used to traverse data structures like matrices and grids. We refer to the loop inside of a loop as the inner loop and the loop the inner loop is contained in as its outer loop. The inner loop is fully executed every time the outer loop is executed. It is convention to start a loop counter at zero and not at one. You will see later why that is.
Loops
Parameterise a for Loop
We refer to the parameter in the declaration of a function as the formal parameter and the actual parameter passed to the function during its execution as the actual parameter or as an argument to the function.
In the lecture we saw how to have a loop execute n times, while n is a parameter. This is often done as we might not know before hand what size a data structure has that we want to traverse. This information is then only available to us once we have received an instance of the data structure as input.
Loops
Increment and Decrement
j = ++i;
1. i = i + 1;
2. j = i;
j = i++;
1. j = i;
2. i = i + 1;
In the previous code example you may have looked at ++i and asked yourself what this does. When working with loops we often have to increment or decrement by one. This is the reason why Java introduces operators that do exactly that.
Two versions of this exists. Pre-increment (shown in the top example to the left) increments the variable first and then assigns the updated value. Post-increment (shown in the bottom example to the left) first assigns the (old) value of the variable and then increments the value.
This is the reason why I personally use ++i in loops, even though it makes no difference to the program correctness itself, as it puts the emphasis on the incrementation rather than the assignment.
You should really understand the difference between the two as many times they are interchangeable, but when they are not you might miss it if you are unsure exactly what the difference is.
Loops
More Shorthand Notation
x = x + 2; x = x - 2;
x += 2; x -= 2;
x = x * 2; x = x / 2;
x *= 2; x /= 2;
x = x % 2;
x %= 2;
Programmers are lazy hence Java contains many shorthand notations for all kind of computations and assignments. Instead of writing i = i + 3 one could for example write i += 3. This works for all operators +, -, *, / and %.
These shorthand notations allow you to write code faster, but there is no need to use them. I personally do not like them all too much (besides ++i and --i).
One can also introduce these operator shorthand notations for logical operators by using that the bitwise operators &, | work the same as && and | | on boolean types and we can thus also write &= and |=. We also have a bitwise xor with the ^ operator.
Loops
Fencepost Error
The print method prints only the string without the newline as println does.
Often when printing the elements inside a structure we separate them using a comma or another separating symbol. We wish only to have such a symbol between two neighbouring elements and not before the first or after the last element. A fencepost error is more general than just printing elements from a data structure. However let us now only consider the case where we are interested in printing the elements of a data structure.
A fence with n sections requires n + 1 fenceposts and in this analogy the fenceposts are the elements and the sections are the separating symbols. Using a for loop and just printing one separating symbol per element in the data structure will give us one separating symbol before the first or after the last element. We must hence either use an if statement to distinguish the first or last for-loop body execution from the rest or we start at the second element and print the first element without a separating symbol as a separate instruction before executing the for loop. Analogous we can also do the same with the last element.
Loops
while Loops
while (condition) {
//statements
}
do {
//statements
} while (condition);
A while loop works very similarly to a for loop but has only a termination condition. The execution of the statements inside the while loop body is what makes (or at least should) the loop terminate. A while loop executes its body until the the condition given to it is not satisfied. The condition is always tested before the loop body is executed.
A while loop can also be written as a for loop with no initialisation statement and update statement and the same loop body. You should not do that but you may do it.
Alternatively to the while loop we also have the do-while loop which first executes the statements in its loop body and then checks if the condition in the loop body is satisfied to determine whether or not to continue executing the loop body.
When taking input from the user we must be able to determine when the input ends and this is where we use so-called sentinel symbols which are designated user inputs to denote the end of the input. Keep this in mind when using loops to retrieve input from the user.
Weakest Precondition
Introduction
{ P }
y = x * x;
{ y >= 0 }
P = x > 0
P = true
We have covered preconditions before and discussed the usage of backwards reasoning to deduce a precondition from a given postcondition using the statements executed between the two. There could be multiple correct preconditions. We are in most cases interested in the one that puts the least amount of restrictions on the variables of the statements executed after the precondition. This is called the weakest precondition.
Formally a precondition P1 is stronger than P2, if given P1 we can follow P2. It hence is more difficult or as difficult to satisfy P1 as it is to satisfy P2.
To the left one can see two preconditions that are correct, however true is weaker than x > 0, as the square of x is also non-negative if x is negative. In fact true is the weakest precondition for the given statements and postcondition. In general there exists no weaker precondition than true, but of course in many cases true is not a valid precondition.
Libraries in Java
Definition
A library in Java is a collection of code bundled together. It gives us utility that we can use without having to implement it ourselves. We will illustrate this by showing the String, Math and Random libraries.
You should wherever possible makes use of libraries as they work well and produce reliable and predictable results (in most cases). Especially when it comes to data structure you should not, besides if told to do so, implement your own data structures if they are available to you through Java libraries. Of course if you want to do that to practice your programming skills and better understand the concepts in the lecture then that is very good and you should, and will do that in the exercises.
Libraries in Java
String Library
Strings are a sequence of characters as we have previously seen. But they are more than just that. String is a type defined in the String class which comes with a lot of utility. We can use the dot notation (method calls preceded by a dot on an object) to call methods from said class.
Instead of listing all methods here we will link to the corresponding Java documentation page as it is a good exercise for you to read about a Java library yourself as you should do that in the future. A lot of my knowledge about libraries greatly improved my skills and speed to solve programming exercises as many methods exists in libraries already and one may not know about that and then implement these methods from scratch. This wastes time especially in the exam.
Libraries in Java
Math & Random Library
The Math library gives you access to functions like sinus, cosinus, absolute value and constants like pi and e. A lot more is defined in the Math library and it is one off the libraries you will often make use of. This class requires no import as the package (what that is will be discussed later) java.lang is always imported by default.
The Random library offers a possibility to create (pseudo) random numbers in a certain range specified by the user. This can be useful whenever you want to try out code you just wrote and do not want to always specify values yourself.
One can see to the left an example that creates a new Random object and then uses it to produce a new random in in the range of 0 (inclusive) and 20 (exclusive). Lower bounds are per convention almost always inclusive and upper bounds almost always exclusive in general.
Visibility
Definition
In Java every variable has its own visibility range referred to as its scope. The scope of a variable depends on where it is defined and what modifiers come with it. We will not cover modifiers here as they will be explained later on in the lecture.
The scope of a parameter of primitive types is only within the method it is a parameter of. If a parameter is a reference variable to an object then the scope can extend beyond the method, i.e. changes made to the referenced object are visible outside the method. Any changes made to primitive type parameters are only visible within the method.
To the left one can see an example of shadowing which happens when two variables have the same name but are not the same variable. It is important to use more than just the name to identify a variable as a variable with the same name may not be the same variable.
The variable x declared just below the class name is in fact not the same variable as the parameter to the method "function". There is a limited number of cases where such shadowing behaviour is possible and even fewer where it is wanted.
Visibility
More on Scope
.png)
The scope of a variable within a method is given by the curly brackets it is surrounded by. In the example to the left one can see that two variables called k are declared and initialised. It does not matter that these initialisations are exclusive to each other, as one can rewrite this code sample with two if statements that can both be true (n == 10 and n % 2 == 0) without causing a problem.
This is the case because both variables are not visible to each other once declared as their scope stays within the curly brackets of the if statements. Understanding scope is important as it will often be used.
One can see that curly brackets inside of curly brackets yield a hierarchical structure to scoping. This hierarchical structure can be seen in the bottom example to the left.
The variable n is visible withing the main method and thus also visible inside all structures inside the method. The variable i is not visible inside the main method besides inside the for loop, the same goes for the variable j. If you were to attempt to print the variable i from outside the for loop this would not work as its scope does not extends outside the for loop.
Shadowing is an exception to this but we can only shadow variables defined as class member variables, i.e. variables that belong to a class. All other variables act according to the scoping behaviour explained above.
Visibility
Consequences
Non-class member variables declared withing the same scope cannot have the same name. This produces an error and your code will not be executed.
Non-class member variables declared outside of each others scope can have the same name. This is because the two variables do not know of each others existence.
A variable is not visible outside of its scope and can thus not be used in any statement.
A variable is visible inside its scope and can thus be used everywhere within its scope.