Further

Object Oriented Programming

“FOOP”

Programming Languages
ECS658U
Matthew Huntbach
matthew.huntbach@qmul.ac.uk
 Programming Languages
• Although we will concentrate on using Java, we will consider
briefly other programming languages
• The emphasis is on general aspects of Object Oriented
Programming that are best illustrated by Java, but apply
similarly to programming in other languages
• Java provides a huge number of built-in classes, we will look
only at a few that have the most general use
• Even with the Java classes we do look at, you will not be
expected to know completely all the public methods they provide
• We will look at how Java originated and developed, and how it
actually works
• We will consider how Java compares with other Object Oriented
Programming languages, such as C++ and Python
• We will mention some JVM languages, programming languages
that compile to the Java Virtual Machine language

2
 Compiling and Interpreting
• Machine code is how programming languages work underneath,
it is the actual physical aspect of computers which stores values
and performs calculations
• When a programming language is compiled that means code
written in that language gets converted to machine code, and
the machine code is then run directly. The program which
converts it is a compiler.
• When a programming language is interpreted that means
instead of it being converted directly to machine code, there is a
program that goes through code in the language and as it does
so it does what is necessary in the computer to run the code.
That program is called an interpreter
• Although any programming language could be compiled or
interpreted, some are designed to be compiled and run that
way, others are designed to be interpreted and run that way

3
 Java Virtual Machine
• Python is an object oriented programming language that is
interpreted, so its code is run directly
• C++ is an object oriented programming language that is
compiled, so to run it you have to use a compiler to produce a
program to do what the C++ program was written for, but directly
using the machine code of the computer it is being run on
• Java is actually between these two. Although Java code has to
be compiled, so a file MyProg.java gets converted to a file
MyProg.class, what is in the class file is code in a language
called Java Virtual Machine, usually shortened to JVM
• JVM is a language that has to be interpreted, but it is close to
machine code, so the interpreter is simple and run quickly
• This makes it easier for Java to be run on different computers
rather than having a separate compiler for each type of
computer

4
 Further use of JVM
• Although the Java Virtual Machine language was introduced just
to assist in getting Java to run on different computers, later on
some other programming languages were designed with
compilers to JVM
• One advantage of this is that those programming languages can
then directly use the built-in code provided as part of Java
• That made it much easier to produce new programming
languages, as the hard work in producing a new programming
language for general use was more providing all the built-in
code that practical use of it needs rather than designing and
implementing its general principles
• As well as this, versions of existing languages were developed
with compilers to JVM, so enabling those languages to be
widely used, and to make use of Java’s built-in code
• For example, Jython is a version of Python that compiles to
JVM

5
 JVM Languages
• Scala is a language that compiles to JVM, it was designed to be
a language similar to Java, but adding some new features
• Many of the features introduced in Scala have now been added
to new versions of Java, but the point of Scala is that unlike new
versions of Java it did not have to provide everything that is in
old versions of Java
• Clojure is a language that compiles to JVM and is otherwise
essentially a modern version of the historical functional
programming language, Lisp
• Groovy is a language designed to compiles to JVM, but like
Python being dynamically typed rather than statically typed, that
is its variables do not have to be declared with types
• Kotlin is a recently developed language that compiles to JVM
which has become successful, with Google now using it as its
preferred language for Android development
• These are just some of the many JVM languages
6
 Machine Code
• A computer will have large amounts of memory where any
section can be accessed just by giving its position
• Computers usually work by having processor registers, places
to store values that can be loaded from and to the memory with
the processors registers then used to do things
• Values are just binary numbers that could represent data, but
can also be treated as mechanical instructions to make the
computer do something, that is machine code
• Machine code will involve simple techniques like taking values
from or putting values to particular places in the memory, adding
two values in the processor registry, choosing a value to use as
the next command to be followed, deciding whether or not to do
something according to what a particular register is set to
• So, compiling means translating what is written in programming
languages to a collection of techniques like this
• In real machine code these are stored just as binary numbers
7
 Assembly Code
• Assembly Code is machine code written in a way that humans
can understand it better
• So in Assembly Code, numbers that are to be used as
commands to make the computer do something are written as
words, and numbers that are numbers are written as decimal
numbers rather than binary numbers
• Assembly Code therefore appears as a list of commands that
are followed one after the other, but some commands will
contain instructions to goto some other command rather than
the following command under some circumstances
• On the next page is written code that is not Assembly Code, but
Java written in a strange way so that it resembles the way that
Assembly Code works
• An array is an actual block of memory, so vals[i] would be
given by the position of vals with the value of i multiplied by
the space of each element added to it

8
 int upto=vals.length, i=0, pos=0, temp=0, command=1;
boolean test = false;
while(command>0)
{
int nextcommand=command;
command=0;
switch(nextcommand)
{
case 1 : test = upto>1; break;
case 2 : if(!test) command=16; break;
case 3 : pos=0; break;
case 4 : i=1; break;
case 5 : test = i<upto; break;
case 6 : if(!test) command=11; break;
case 7 : test = vals[i]>vals[pos]; break;
case 8 : if(test) pos=i; break;
case 9 : i++; break;
case 10 : command=5; break;
case 11 : upto--; break;
case 12 : temp=vals[upto]; break;
case 13 : vals[upto]=vals[pos]; break;
case 14 : vals[pos]=temp; break;
case 15 : command=1; break;
case 16 : command=-1;
}
if(command==0) command = nextcommand+1;
}
}
9
 Java’s switch statement
• Java’s switch statement is headed by switch(var), and
when executed starts at the code given by case v where v is a
constant value equal to the current value of var
• var can be an int or a String or an enum value – we will
look at what enum values are later
• Instead of just doing what is at case v, a switch statement will
carry on with the following cases unless it is halted by break
• It can also have a case given by default which it goes to if
var is not any of the values which have a case statement
• Here is Java’s official explanation of it:
https://docs.oracle.com/javase/tutorial/java/nutsandbolts/switch.html
• A switch statement is the closest Java has to a goto
statement, but it is meant just for use where it would be more
convenient than having a lot of if statements for testing values
of var

10
 The switch statement example
• The switch statement example given is not meant to be a good
example of the use of switch
• Its purpose is to show how hard it is to see what some code will
do if it consists just of a list of short statements with a goto that
means it may be switched to another statement rather than the
next one
• So command is the position of the next statement to be
executed, the while loop and code outside the switch
statement is just there to make command get set to the next
value if it was not reset, in assembly code that would be done
automatically
• Structuring code using while loops and if-statements which
can have compound statements inside them make code easier
to understand by looking at it
• For actual execution with compilation, they do get transformed
into code consisting of a list of simple statements with
equivalent of goto to change which would be the next one

11
 Equivalent of what the switch
statement example would do
public static void sort(int[] vals) {
int upto = vals.length;
while(upto>1) {
int pos=0;
int i=1;
while(i<upto) {
if(vals[i]>vals[pos])
pos=i;
i++;
}
upto--;
int temp=vals[upto];
vals[upto]=vals[pos];
vals[pos]=temp;
}
}

12
 Code without indentation
public static void sort(int[] vals) {
int upto = vals.length;
while(upto>1) {
int pos=0;
int i=1;
while(i<upto) {
if(vals[i]>vals[pos])
pos=i;
i++; }
upto--;
int temp=vals[upto];
vals[upto]=vals[pos];
vals[pos]=temp; }
}

Java would treat this as exactly the same as the previous code.
A new line character is treated the same as a space character,
multiple space characters are treated as a single space character
13
 Code with different variable names
public static void sort(int[] a) {
int b = a.length;
while(b>1) {
int c=0;
int d=1;
while(d<b) {
if(a[d]>a[c])
c=d;
d++;
}
b--;
int e=a[b];
a[b]=a[c];
a[c]=e;
}
}
Java would treat this exactly the same as the previous code, but for
human programmers it is harder to understand, as the names here
do not give an indication of what each variable is used for
14
 Good Quality Code Basics
• Indentation is putting spaces in front of lines of code to display its
structure
• The reason it should be done is that it makes it easier for human
programmers to pick up the structure of code when they look at it
• So, code which is part of a loop is put further to the right under the
loop header to make it clear when looking at it to see which parts are
part of the loop
• Similarly with code that is executed in an if statement when the test
of it evaluates to true and after else when it evaluates to false
• Using variable names that indicate what a variable is being used for
makes it easier to see at a glance how the code works, perhaps
maxSoFarPos should have been used rather than pos
• Some short variable names have a convention of a standard use,
with i and j as indexes being an example
• As it is standard to use i for this, no variable should be named i if it
used for something else rather than as an index
15
 Splitting into more methods
• It can make code easier to understand if parts of the code are
put into separate methods, for example:
public static void sort(int[] vals) {
int upto = vals.length;
while(upto>1) {
int pos = biggestBelow(upto,vals);
upto--;
swap(vals,upto,pos);
}
}
• Once a method becomes complex, with multiple statements
inside multiple statements, consider taking a statement out and
making it into a separate method with a name that indicates
what it does
• Also this will help avoid repeated code if the same assistant
method could be called in more than one place, this makes code
easier to understand and modify
16
 Assistant methods
private static void swap(int[] array, int pos1, int pos2) {
int temp=array[pos1];
array[pos1]=array[pos2];
array[pos2]=temp;
}

private static int biggestBelow(int limit, int[] array) {

int pos=0;
int i=1;
while(i<limit) {
if(array[i]>array[pos])
pos=i;
i++;
}
return pos;
}
• As mentioned previously, methods that are only to assist other
methods should be declared as private
• An assistant instance method that is not private could enable
other code to do things it should not be able to do directly
17
 Comments
private static void swap(int[] array, int pos1, int pos2)
// In array, sets what was at position pos1 to what was
// at position pos2 and vice versa
…

private static int biggestBelow(int limit, int[] array)

// Returns the highest value integer in the portion of
// array up to but not including the position given by limit
…
• Programming languages have symbols that indicate comments,
meaning text that will not be used by the computer
• Comments to explain the purpose of a method, or how it works,
can be helpful for human programmers when modifying the code
• However, large amounts of comments can make the structure of
code harder to see
• Giving methods clear names that explain what they do, and
variables names that explain their purpose, and splitting code into
well named methods makes the need for comments less
18
 Python Equivalent
def sort(vals) :
upto = len(vals)
while(upto>1):
pos=0
i=1
while(i<upto):
if(vals[i]>vals[pos]):
pos=i
i+=1
upto-=1
temp=vals[upto]
vals[upto]=vals[pos]
vals[pos]=temp
• In Python, what is inside a statement is everything below its
header which is further indented
• So upto-=1 is in the outer while loop but not the inner while
loop
• Variables are not declared, they are just used and are new
variables if they were not previously used
19
 A Python Feature
• The Python code could be written as:
def sort(vals) :
upto = len(vals)
while(upto>1):
pos=0
i=1
while(i<upto):
if(vals[i]>vals[pos]):
pos=i
i+=1
upto-=1
(vals[upto],vals[pos])=(vals[pos],vals[upto])
• This shows a feature that Python has, an assignment of the form
(x,y)=(val1,val2) assigns x to val1 and y to val2
simultaneously
• If val1 or val2 contain x or y, it will be their values before the
assignment that are used
• So (x,y)=(y,x) works to swap the values of x and y
20
 Compound Statement
• To summarise, in Java a while statement takes the form:
while(test)
statement
where statement is a single statement, meaning that
statement1
while(test)
statement2
statement3
would compile to
1: statement1
2: if(!test) goto 5
3: statement2
4: goto 2
5: statement3
• However, surrounding a list of statements by { and } causes it
to be a single compound statement
• That is why { and } can be omitted if what is inside a while
statement is just a single assignment or method call
21
 Using { and }
• Similarly, an if-else statement takes the form:
if(test) statement else statement
so
statement1
if(test) statement2
else statement3
statement4
would compile to
1: statement1
2: if(!test) goto 5
3: statement2
4: goto 6
5: statement3
6: statement4
• Use of { and } when they surround a single statement can
make code look more complex
• The way Python uses indentation for why Java uses { and }
helps make Python code look simpler
22
 The C and C++ Programming Languages
• The programming language called C resembles Java in terms of the
way statements are structured but with no object-oriented aspects
• A C program looks like a Java program but with all methods the
equivalent of Java static methods
• C has some features which Java does not have, giving it direct
access to the actual storage of the computer
• So, C is like assembly code made more readable by structuring it
with loops and methods, it is therefore called low level
• The C++ programming language developed the C language by
adding object oriented features, but also keeping the low-level
features of C
• The object-oriented features of C++ were found to be very
convenient in structuring code
• Java was developed from C++ by taking away the low-level features,
and using compiling to JVM rather than directly to machine code

23
 Low level features of C and C++
• Although C and C++ use the same loop statement structuring as Java,
they also have a goto statement that allows code to break that and
switch from one place to any other place in the code
• You can access and change data directly as it is stored in the
computer rather than through the type given to it originally
• In C and C++, if pos is a variable of type int*, it stores the position
of a variable of type int, and if num is a variable of type int then
&num gives the value which is the position of the variable num
• So the assignment pos=&num sets pos to store the position of num
• Then *pos=100 will change num to store 100 because *pos means
the variable that pos gives the position of
• Also *pos=val sets whatever is the position given by pos to the
value stored in the variable val of type int
• The symbols * and & can be used with any type, not just int
• If pos is the address of a[0] where a is an array then pos+1 is the
address of a[1]
24
 C Structures
• Although C does not have classes, it does have structures, which are
like objects which have variables but no methods
• For example:
struct Student {
String name;
int num;
int marks[];
}
defines a type Student which contains a String, an integer and an
array of integers
• Here, if std is a variable of type Student, std.name, std.num and
std.marks have to be used directly to access the String, int and
array inside the structure stored in std
• Note also that in C the array of int values has to be declared by using
int and following the variable name with []
• The C way of declaring arrays can also be used in Java, but there is
no good reason to do so, you should use int[]
25
 Java compared with C
• Writing classes in Java like C structs, that is just with variables
inside, no methods, can be an indication of not having properly learnt
object oriented programming
• That is still the case if all variables have getters and setters and that is
the main way classes are used
• An important thing to understand is that in Java primitive types (int
and other numbers) store values directly, but all other variables store
references to objects, not objects directly
• So if you defined a class Student in Java identical to the struct
called Student given above, the type Student in Java would be
what the type Student* is in C
• This is a fundamental aspect of programming that many do not pick up
properly, leading to programming mistakes later
• Using the C style for declaring arrays can also be an indication of
someone who has not properly learnt to program in Java, and in reality
is still using what was used decades ago to teach programming in C

26
 Java compared with C++
• Similar applies to C++, a class variable stores the data of an object of
the class directly, whereas in Java a class variable stores a reference
to an object
• A reference to an object is actually its position, but in Java it cannot be
accessed directly and modified using it like an integer, Java does not
have the equivalent of the * and & used for this in C and C++
• The reason for using C++ rather than Java is that being able to access
and change the actual data as stored in the computer can be used to
produce more efficient code
• Also more efficient because C++ compiles directly to machine code
rather than to JVM which then has to be interpreted
• This can make C++ code less safe and possibly having difficult errors,
as it means the rules of object oriented programming can be broken
• Early Java did run much slower than C++, but modern versions have
put in various aspects in how it works underneath that make it work as
quickly as C++ in most cases
• Python, being just interpreted, is still much slower
27
 Variable referring to objects
• For this module, you do not need to know the details of how C++
works, just the concepts given, as general programming issues
• What you do need to know, and be familiar with, is the way that, in
Java, variables that are not of a primitive type always refer to objects
• In Python, all variables refer to objects
• So, in Java and Python it is important to understand that if var1 and
var2 refer to objects, the assignment var2=var1 causes var2 to
refer to the same object that var1 refers to
• It is important to understand that this is not copying an object, it means
that if you then do var2.meth(arg), where meth is a method that
cause a change to the object it is called on, it will change what var1
refers to as well, because they are the same object
• If you then did var1=var3, it does not change what var2 refers to, as
var2 continues to refer to what var1 used to refer to, so after that
var2.meth(arg) does not change what var1 refers to

28
 Variables as arguments to methods
• It is important to understand that in Java, if a value of an object type is
an argument to a method, what that means is that a reference to the
object is passed, not the data of the object copied and passed
• A variable inside the method call is then set to refer to the same
object, but it is a separate variable local to the method call
• So, for example, if a method signature is:
static Thing buy(Account acc)
then a call myThing=buy(myAcc) results in a variable called acc
referring to what the variable myAcc refers to, and if a call
acc.reduce(val) changes what is in what acc refers to, it also
changes what is in what myAcc refers to, as it is the same object
• However, if there is an assignment acc=acc1 in the method, after that
acc no longer refers to what myAcc refers to, it does not cause myAcc
to refer to what acc1 refers to, so after that acc.reduce(val) will
not change what is in what myAcc refers to
• Similarly, myThing is set to a reference to a method that is returned
29
 Variables not passed or returned
• A common issue for those who have just learnt about OOP is not to
properly understand this, and so talk about “variables passed to
methods” or “variables returned”
• This results in the incorrect belief that acc in the method call above
becomes another name for the variable called myAcc
• However, if the class Account is such that it is possible to access a
variable inside the object, then there are two names for the same
variable
• For example, if there is a variable amount inside an object of class
Account, then acc.amount and myAcc.amount are two names for
the same variable inside the object, so then an assignment
acc.amount=value will also cause myAcc.amount=value to
happen
• As it is so important that this is properly understood for anyone to be
able to claim that they really do understand OOP, we will go into more
details about these issues later

30
 Object Oriented History
• Object Oriented Programming originated in a language called Simula,
designed for special use to write programs that simulate real world
events, so an object would represent a real world object
• Objects used for this purpose still tend to be used to introduce OOP
• While some objects in OOP will be of this sort, others are more
abstract, such as generalised collection types
• C++ was C with OOP aspects introduced
• The success of C++ was because of the way it worked well to divide
code into well defined separate parts, with inheritance also assisting
by allowing generalised code to be written
• Java took this further by making sure different parts of code could only
interact in a limited way, this making it more clear how code worked,
reducing the possibility of errors, making it easier to modify code
• C# is another programming language based on adding OOP aspects
to C, but done in a way like Java that takes out the low-level aspects

31
 Java Versions
• Java has gone through many versions
• Initially the versions were called Java 1.1, Java 1.2, and so on
• Java 1.5 became called Java 5, and then versions were called Java 6,
Java 7 and so on
• Each new version of Java is produced in a way that means code
written for previous versions will still compile and run in the same way
• New versions of Java may introduce new built-in code, and new ways
in which it can be used
• Old built-in code is not taken away, but it may be described as
deprecated, meaning you are advised not to use it, as something new
has been introduced which provides what it was for in a better way
• An important new version of Java which added a feature needed to be
understood in basic programming was Java 5, which added type
variables
• Java 8 also added key new features which basic programmers should
know about, which allow a functional programming style to be used
32
 Functional Programming
• Functional programming originated very early, with the language Lisp
placing an emphasis on programming expressed abstract way rather
than directly manipulating computer storage
• The mathematical notation lambda calculus (λ-calculus) originated
before computers existed but can be considered the most basic aspect
of functional programming
• The basic concept is variables that store functions, where a function is
a method that takes arguments and returns a result, and does this
without changing the value of any variables
• For many years, functional programming was mainly used in academic
research, but recently it has become more widely used in industry
• That is shown by lambda expressions being introduced as a new
feature in the version of Java called Java 8
• Haskell is the most widely used pure functional language developed
academically, which has influenced more general languages
• See: http://learnyouahaskell.com/chapters for more on Haskell
33
 Immutable Objects
• An important aspect of Haskell as a pure functional language is that
variables cannot have their values changed
• A functional style of programming in OOP languages would be having
methods that take arguments and return values, but do not make any
changes to the object they are called on or to objects passed as
arguments
• A functional style of programing in OOP is taken further by having
immutable objects, that means objects which have no methods that
can be called on them to change them
• With an immutable object, a computation is done by creating and
returning a new object rather than changing an object
• This has an advantage, as you can safely share objects that are
immutable because no code that shares it can change it
• If two pieces of code share a reference to an object that is mutable
rather than immutable then one piece of code changing the object
could cause problems if it was not realised in the other piece of code
that this could happen
34
 A String is an Immutable Object
• An example of an immutable object in Java is String, there are no
methods in class String that change the actual String they are
called on
• For example str.toUpperCase() returns a new String which is
like the one that str refers to but with lower case letters replaced by
the equivalent upper case
• That means if str refers to "FredBloggs" then
str1=str.toUpperCase() sets str1 to refer to "FREDBLOGGS" but
str still refers to "FredBloggs"
• If you just had a statement
str.toUpperCase();
it does nothing because the new String returned is ignored
• The statement str=str.toUpperCase(); will change str to refer
to "FREDBLOGGS" but that is because the variable is reassigned to a
new object, not because the actual object it referred to was changed
• So if str2=str happened before, str2 would still refer to
"FredBloggs"
35
 Lazy Evaluation
• Another important aspect of Haskell, and some other functional
programming languages, is lazy evaluation
• What this means is that a function call is made and its value returned
only if that actual value is needed
• If a function call is used as an argument to another function, but that
function does not make use of it, it is not calculated
• This has an advantage because if a value that would take a long time
to calculate but is not actually used is not calculated, it would save
time
• Java does not use lazy evaluation in general but is has been
introduced in the way Java’s Stream class works
• The Stream class in Java was introduced in Java 8 as an aspect of
enabling Java to be used in a functional programming style
• This is something we will look at later
• However, one aspect of Java that is a form of lazy evaluation that was
always in existence is the way && and || work

36
 && and || in Java
• In Java, a&&b is “a and b”, so it evaluates to true if both a and b
evaluate to true, otherwise it evaluates to false
• a||b is “a or b”, so it evaluates to true if either a or b evaluate to
true, and evaluates to false only if both a and b evaluate to false
• a and b could be method calls that return a boolean value
• How it works is that with a&&b, if the method call a returns false,
then the method call b does not take place because whatever it would
return if it did, a&&b is still false
• With a||b, if the method call a returns true, then the method call b
does not take place because whatever it would return, a||b is still
true
• For example, if p1 and p2 are of a type with a method that can be
called on them with signature boolean ask(Question q), then if
p1.ask(q1)&&p2.ask(q2) is used, the call p2.ask(q2) would not
be made if the call p1.ask(q1) returned false

37
 & and | in Java
• In an OOP language, a method call can do something else as well as
return a value, so if you wanted the other things that p1.ask(q1) and
p2.ask(q2) to be done in all cases, you could do
boolean a=p1.ask(q1), b=p2.ask(q2);
and then use a&&b or a||b
• With full lazy evaluation that would still not work because in that case
the assignment to a variable is only evaluated when the value of the
variable is used
• In a pure functional language like Haskell, method calls do not do
anything other than return a value, so lazy evaluation could never
cause a problem
• In Java, the symbols & and | are the symbols for “and” and “or” in the
way Java works otherwise, so a&b evaluates to true if both a and b
evaluate to true and a|b evaluates to true if either a or b evaluate
to true, and in all cases both a and b are fully evaluated
• So p1.ask(q1) & p2.ask(q2) will always call p2.ask(q2) after
calling p1.ask(q1) regardless of what p1.ask(q1) returns
38
 Side Effects of Method Calls
• What we have seen in this example is the issue of side effects of
method calls
• Java, as a pure OOP language takes away some of the side effects
that C++, being OOP added to the low-level language C can cause
• However, Java method call can still have side effects, meaning doing
something else as well as returning a value
• It can often be the case that a method call represents an action that
both returns something and changes the object it is called on
• Or it may be that the main purpose of a method call is to change an
object, so what it returns is just information about that, an example
being a method like add or remove in class Set which returns a
boolean value saying whether the set was changed
• Pure functional programming has no side effects, so the equivalent of
add or remove on a set would work by returning a new set rather than
changing an actual set
• Java’s built-in collection classes work by methods that change the
actual object they are called, so not a functional style
39
 Functional Style Programming
• The main point here is to understand and be able to use a functional
style of programming, as methods without side effects can lead to
code where you can be more sure it will always work correctly
• When writing code you need to decide whether it would work best by
creating and returning new objects rather than making changes to
actual objects
• However, code that always worked by creating and returning new
objects could be very inefficient
• For example, implementing a set collection so that every time an
element is added or removed that is done by creating a new set would
be very inefficient is that meant creating a complete new array to
represent it each time
• There are other ways of representing collections, some of which
enable a more functional style to be implemented, we will look at this
later, and you may also have seen examples in the Algorithms and
Data module

40
 Two Variables Referring to
the Same Object
• If there are side effects, an issue that needs to be considered when
you do something like p1.ask(q1) & p2.ask(q2) is the possibility
of two variables referring to the same object
• That would be the case if there had been a previous assignment
p2=p1 and no further assignment of p1 and p2 after that
• Or if this was inside a method with a header such as
boolean askTwo(Player p1, Player p2)
and the call to it was askTwo(p,p)
• That would then cause the same as p.ask(q1) followed by
p.ask(q2) to happen
• If the call of ask makes a change to the Player object it is on, and
that affects what happens with a second call of ask, that could cause
the code to behave in an unexpected way if you had not considered
the possibility of p1 referring to the same object as p2 refers to
• So an advantage of pure functional programming is that because it
does not have side effects, there are no problems like this
41
 Loops Require Change
• An issue with pure functional programming is that it cannot use loops,
as they require actual changes made to variables or objects
• Consider the loop of the form:
while(test)
statement
• How this works is to repeatedly execute whatever is statement until
whatever is test evaluates to false
• Since test is exactly the same code each time using the same
variables, what is in statement must cause at least some times
change to a variable in test so that at some point it evaluates to
false when previously it evaluate to true
• Mostly this would be reassigning a variable, but if test took the form
obj.meth(val) which returns a boolean, it would still work if
statement did not change the value of val but made a call such as
obj.change(arg) which did something to the object that obj refers
to that causes meth(val) called on it to return false where
previously it returned true
42
 Loop expressed as Recursion (1)
• Here is a simple example of a loop relying on an object being changed
rather than a variable:
int countBuy(Account acc, Thing t) {
int count=0;
while(acc.buy(t))
count++;
return count;
}
• It counts the number of time acc.buy(t) can be called, we can
assume the call reduces the amount in the Account referred to by
acc until it is not enough to buy what t refers to
• Here a recursive equivalent:
int countBuy(Account acc, Thing t) {
if(!acc.buy(t))
return 0;
return countBuy(acc,t)+1;
}
43
 Loop expressed as Recursion (2)
• Looking at the recursive equivalent again:
int countBuy(Account acc, Thing t) {
if(!acc.buy(t))
return 0;
return countBuy(acc,t)+1;
}
• An important thing to understand is that this is different from the loop,
because each call of countBuy(acc,t) has its own variables called
acc and t, although these variables are all set to refer to the same
objects
• This is not completely functional, because it requires acc.buy(t) to
change the single object that every acc variable is set to refer to, so
that eventually the call returns true rather than false
• A completely functional method would work by sending a different
Account object to each recursive call
• The same Thing object can be sent, but that is under the assumption
that acc.buy(t) does not change the actual object that t refers to
44
 Loop expressed as Recursion (3)
• Here is the recursive equivalent which does work in a completely
functional way, so long as the object t refers to does not get changed
by any of the method calls:
int countBuy(Account acc, Thing t) {
if(!acc.canBuy(t))
return 0;
Account acc1 = acc.buyA(t);
return countBuy(acc1,t)+1;
}
• The method buyA works like the method buy, but instead of changing
the actual Account object it is called on, it returns a new Account
object representing the change to the account caused by buying
• There is also a separate method canBuy that returns a boolean
saying whether its argument can be bought using the Account it is
called on
• This is not very sensible code, so you can take it as illustrating that
while it is often a good idea to use a functional style with immutable
objects, it is not always the case that that is the best way to program
45
 Tail Recursion (1)
• Many when asked to write a recursive version of this:
int countBuy(Account acc, Thing t) {
int count=0;
while(acc.buy(t))
count++;
return count;
}
would write:
int countBuy(Account acc, Thing t, int count)
if(!acc.buy(t))
return count;
return countBuy(acc,t,count+1);
}
• This is wrong, because if you are asked to write a method you should
give it only the arguments it was meant to have

46
 Tail Recursion (2)
• This is what should be done
int countBuy(Account acc, Thing t) {
return countBuyRec(acc,t,0)
}
int countBuyRec(Account acc, Thing t, int count)
if(!acc.buy(t))
return count;
return countBuyRec(acc,t,count+1);
}

• That is, if recursion requires an extra argument to represent something

that changes, put the recursion in an assistant method, with the call to
it giving the initial value of the variable as its argument
• This is tail recursion, meaning recursion where what is always
returned is just the result of the recursive call rather than doing
something with the recursive call
47
 Tail Recursion (3)
• Tail recursion is the more direct equivalent to the loop, although there
is a separate variable count in each recursive call rather than a single
variable called count that gets its value changed
• The recursive method we saw before:
int countBuy(Account acc, Thing t) {
if(!acc.buy(t))
return 0;
return countBuy(acc,t)+1;
}
means that each call of countBuy apart from the one that returns 0
waits for the recursive call it made to finish and then carries on adding
1 to it to get what it returns
• If you write complex tail recursive code when there is simpler recursive
code that is not tail recursive, it may be an indication that you are still
really thinking in terms of loops rather the actual recursion

48
 Thinking Recursively
• In the countBuy example, there is no real good reason for doing it
recursively, the loop code for it is more efficient, and more obvious
• However, in other cases, being able to think recursively is very helpful
• Skilled programmers will often think of solutions naturally using
recursion, and then if it makes sense convert them to loops
• So using functional programming, which forces you to switch to using
recursion, can help you become a better general programmer
• You can also get used to recursion by using a functional style in a
language like Java, and that is one reason why will look at
programming using LispList<E>
• The basic concept of recursion is to think of solving a problem by
breaking it into parts, one or more of which are smaller versions of the
same problem, and using the solution to those parts to solve the whole
problem
• An obvious example is the more efficient algorithms for sorting: split a
collection into two parts, sort the two parts, and join them together to
get the complete sorted collection
49
 Efficient Sorting of Arrays in Java
public static void sort(String[] vals) {
if(vals.length<=1)
return;
int mid=vals.length/2;
String[] vals2 = new String[mid];
if(mid*2<vals.length)
mid++;
String[] vals1 = new String[mid];
for(int i=0; i<mid; i++)
vals1[i]=vals[i];
for(int i=mid; i<vals.length; i++)
vals2[i-mid]=vals[i];
sort(vals1);
sort(vals2);
int j=0, k=0;
for(int i=0; i<vals.length; i++)
if(j==vals1.length)
vals[i]=vals2[k++];
else if(k==vals2.length)
vals[i]=vals1[j++];
else if(vals1[j].compareTo(vals2[k])<0)
vals[i]=vals1[j++];
else
vals[i]=vals2[k++];
}
50
 Merge Sort (1)
• The algorithm used in the previous slide was Merge Sort
• Merge sort works by dividing a collection into two parts of equal size, it
doesn’t matter which element goes into which part
• Then merging the two sorted parts means going through both of them,
putting into the sorted collection whatever is the lowest element of
either not yet put into the sorted collection
• That is what this part of the merge sort code did:
int j=0, k=0;
for(int i=0; i<vals.length; i++)
if(j==vals1.length)
vals[i]=vals2[k++];
else if(k==vals2.length)
vals[i]=vals1[j++];
else if(vals1[j].compareTo(vals2[k])<0)
vals[i]=vals1[j++];
else
vals[i]=vals2[k++];
• This could have been in a separate method, with a call to it:
merge(vals,vals1,vals2);
51
 Merge Sort (2)
• The separate method would have signature:
private static void merge(String[] vals,
String[] vals1, String[] vals2)
with the requirement that vals1 and vals2 are already sorted, and
the length of vals is the length of vals1 and vals2 added
• Comments could also be put in the code to explain how it works
• It may still not look very clear because of the way it changes an actual
array, it looks more clear when done in a more functional style
• The alternative way of implementing merge sort with code that works
by changing the contents of the actual array passed to it rather than by
returning a new sort array would start with:
public static void sort(String[] vals) {
sort(vals,0,vals.length);
}
with the assistant method that does all the work having signature:
private static void sort(String[] vals, int from, int to)
52
 Merge Sort (3)
private static void sort(String[] vals, int from, int to) {
if(to-from<=1)
return;
int mid=(from+to)/2;
sort(vals,from,mid);
sort(vals,mid,to);
int j=from, k=mid, num=to-from;
String[] vals1 = new String[num];
for(int i=0; i<num; i++)
if(j==mid)
vals1[i]=vals[k++];
else if(k==to)
vals1[i]=vals[j++];
else if(vals[j].compareTo(vals[k])<0)
vals1[i]=vals[j++];
else
vals1[i]=vals[k++];
for(int i=0; i<num; i++)
vals[i+from]=vals1[i];
}

53
 Arrays and ArrayList<E>s
• What we have looked at is sorting arrays directly in Java
• This can look quite complex, as arrays are of a fixed size
• An array in Java, as in C and C++, means a piece of actual computer
memory of its size, that is why its size cannot be changed
• So using arrays directly is really low-level programming
• For general programming, it is better to use ArrayList<E> which is
an object that works like an array, but with method calls rather than
the use of the symbols [ and ]
• If list is of type ArrayList<Atype> and arr is of type Atype[],
then list.set(i,val) is equivalent to arr[i]=val, and
list.get(i) used in an evaluation is equivalent to using arr[i]
• But there are also other methods like list.add(val) which do
change the size of the collection that list refers to, it increases the
size by one and puts val in the new position added
• This makes code easier to follow than direct use of arrays
• ArrayList<E> does use arrays underneath, we will look at this in
detail later
54
 If-then-else
• Java’s if-else statement
if(test)
statement1;
else
statement2;
works under the basis that statement1 and statement2 cause
something to happen
• Haskell’s if-then-else evaluates to a value, for example
sol = if test then val1 else val2
• Java has the equivalent of Haskell’s if-then-else statement, it is
test ? val1 : val2
• So in Java if(test)
sol=val1;
else
sol=val2;
can be written as:
sol = test ? val1 : val2;
55
 Java’s ? :
• You could even write:
int j=0, k=0;
for(int i=0; i<vals.length; i++)
if(j==vals1.length)
vals[i]=vals2[k++];
else if(k==vals2.length)
vals[i]=vals1[j++];
else if(vals1[j].compareTo(vals2[k])<0)
vals[i]=vals1[j++];
else
vals[i]=vals2[k++];
as: int j=0, k=0;
for(int i=0; i<vals.length; i++)
vals[i] = j==vals1.length ? vals2[k++] :
k==vals2.length ? vals1[j++] :
vals1[j].compareTo(vals2[k])<0 ? vals1[j++] :
vals2[k++];
• You can use test ? val1 : val2 directly as a method argument, so
meth(test ? val1 : val2, x); is the equivalent of
if(test) meth(val1, x); else meth(val2, x);
56
 Functional Language Method Calls
• What in Java is written meth(val1,x) is in Haskell, and other
functional programming languages, as meth val1 x
• An important point is that you could write just meth val, and this
returns a function which takes one argument and works like the call of
meth with its first argument set to val1
• So, if meth in Java is:
int meth(int a, int b) {
if(b>a*10) return b; else return a;
}
then mf = meth 5 in Haskell results in mf being the equivalent of:
int mf(int b) {
if(b>50) return b; else return 5;
}
in Java
• That is, any call mf x after that is the equivalent of a call meth 5 x
57
 Lisp Lists
• In Lisp, lists were produced by the following:
– cons val ls returns a new list with val added to the front of
what is given by ls
– car ls returns the first element in the list given by ls
– cdr ls returns a new list consisting of all the elements of the list
referred to by ls except the first one
• In more modern versions, head is used rather than car and tail is
used rather than cdr
• Note the difference between this and Java
• If ls is of type List<E> in Java, then ls.add(0,val) adds val to
the front of the list referred to by ls, but it changes the actual list
rather than creating and returning a new list
• In Java ls.remove(0) removes the first element from the list
referred to by ls, but changes the actual list rather than returning a
new list

58
 Lists in Java
• We will consider this further later, by considering a class
LispList<E> with methods cons, head and tail, which works like
functional languages lists, that is constructive rather than destructive
• Note that in Java ls.subList(1,ls.size()) does return a new
List<E> object which contains all elements of the list referred to by ls
except the first one
• However, an important issue of this is that what it returns is a list that
shares the actual internal content of what ls refers to
• So, consider that ls is of type List<Integer> and refers to a list
that could be written as [10,20,30,40]
• If we then did ls1=ls.subList(1,ls.size()) the variable ls1
would refer to a list that could be written as [20,30,40]
• But if we then did ls.set(2,99) it would not only change ls so that
it refers to [10,20,99,40], it would also change ls1 so that what it
refers to is [20,99,40]
• It is important to understand issues like this to be a Java programmer
59
 Summary
• How computers work underneath has not changed much over the
years, but the programming languages used to do it have
• The point is to make it easier for humans to understand how the code
works, although underneath is still uses machine code
• Using names for storage places and commands, and expressing
numbers digitally rather than in binary form is the first issue
• Then structuring code into named pieces rather than using goto
• Then naming structures of code as methods to make it easier to be
able to use them in multiple places rather than repeat code
• This is taken further by linking methods and variables they make use
of in classes defining objects
• An important issue, developed in OOP, is limiting the way different
parts of code can interact, to make it more clear how code will work
and avoid unexpected effects that are hard to see
• Functional programming is another approach, starting off thinking
mathematically rather than starting off thinking as machine code
60
 Java
• The main thing we are covering in this module is good ways of
structuring code to make it clear how it works, with well defined
separate parts, and generalised code to enable a part to be re-used
rather than copied and the copy changed
• Java works well to illustrate these general principles, so this module
will concentrate on using Java for this reason
• We will concentrate on those aspects of Java that illustrate more
general principles of programming that apply to other languages
• Java can be considered as in between the very abstract way of
programming given by functional programming languages, and
programming which is still quite closely based on how computer
hardware works underneath
• We will use examples of Java code that work well to illustrate
principles of programming rather than because they are the best way
to write code for real use
• Many aspects of programming that have already been taught need
more examples to make sure you do really understand them properly
61