Lecture 1: Introduction To Programming in Java Lecturer: Susan Eisenbach Textbooks Software Is Required
Lecture 1: Introduction To Programming in Java Lecturer: Susan Eisenbach Textbooks Software Is Required
Lecture 1: Introduction To Programming in Java Lecturer: Susan Eisenbach Textbooks Software Is Required
Functional versus
imperative languages A statement written in Java print() and println()
Functional languages are ideal for expressing the println("Write this in Haskell!");
functional (the problem to be solved) component of any Text can be printed on the screen using
problem however... print() or println().
at least 50% of all programs deal with input/output Commented version
rather than a problem and functional languages aren’t /* Susan Eisenbach
Using println(" ") puts a carriage
very good at input/output.
every statement is
return on the end of the line.
Think of the programs you use now:
* 12 November 2007 print( "7*3" );
editor * a bit of bravado terminated with a ;
println( "=" ); println( 7 * 3 );
mail
language translator (Haskell or Java)
*/ This code prints:
web browser String exclaim = "Write this in Haskell!"; 7*3=
Functional programming should have taught you to println(exclaim); 21
appreciate concise elegant programs.
4 5 6
Concatenating output with + Comments A function written in Haskell
String drink = "slammers"; There are two ways of commenting code. bigger :: Int -> Int -> Int
print("I like "); println(drink); // comments are terminated by the end of line -- post: returns the larger of two numbers
argument types
This code prints: I like slammers // Susan Eisenbach bigger a b|a>b = a
// 12 November 2007 |otherwise = b
println("I like Tequila " + drink); // a bit of bravado arguments
This code prints: I like Tequila slammers /* comments in Java are also terminated by */ Same method written in Java
println /* Susan Eisenbach
int bigger(int a, int b){
("6/9 = " + 6/9 + " or " + 6.0/9.0); * 12 November 2007
//post: returns the larger of the 2 values
* a bit of bravado
This code prints: */ good to make several
if (a > b) {return a;}
6/9 = 0 or 0.6666666666666666 else {return b;}
lines of comments stand
}
out in your program
7 8 9
16 17 18
Summary Revision from Haskell
The syntax of the Java programming language Define the base case(s)
is introduced in this course for coding
solutions to the problems set. Define the recursive case(s)
We have seen Lecture 2: Recursion – Split the problem into subproblems
– methods (Haskell functions) with { } – Solve the subproblems
– statement terminators - ; – Combine the results to give required answer
– variables Lecturer : Susan Eisenbach
– conditionals – if (predicate) {…} else {…}
For extra material read parts of
– assignments
– input/output chapters 1,3 and 11
– main method of
– complete Java program
Java Software Solutions
19 Susan Eisenbach 20 21
Haskell program -> Java method becomes: What does assert do?
divisor :: Int -> Int -> Int int divisor (int a, int b){ assert (a > 0 && b > 0):
--pre: the arguments are both assert (a > 0 && b > 0): "divisor must be given arguments > 0";
"divisor must be given arguments > 0";
-- integers > 0
//post: returns the gcd of a and b
--post: returns the greatest common divisor if (a == b) {return a;} evaluates the predicate
divisor a b | a==b = a else {if (a > b) {return divisor (b, a - b);} true? – continue to execute the code
| a>b = divisor b (a-b) else {return divisor (a, b - a);}} false? – print the string on the screen and
| a<b = divisor a (b-a) } stop the program
Do not execute code which you know may crash or loop
forever.
22 23 24
When should you have an assertion? Haskell program -> Java method Java method -> Java program
void main(){
If you write a method that expects something special fact :: Int -> Int
print("Factorial number that you want? ");
of its inputs then you need to put as a precondition --pre: n>= 0
println("Answer = " + fact(readInt()));
whatever needs to be true before the code can be run. --post: returns n!
}
The precondition should be coded (if possible) as an fact 0 = 1
int fact( int n ){
assertion. fact (n+1) = (n+1)* fact n
assert (n>= 0):
becomes :
Assertions can also be written without the String "factorial must be given an argument >= 0";
message. In this case, if the assertion fails then your
int fact( int n ){
//post: returns n!
program stops with an AssertionError.
assert (n>= 0 && n < 17):
if (n==0) {return 1;}
"factorial must be given an argument >= 0";
If the user has given a method arguments that meet //post: returns n!
else {return n*fact(n-1);}
the precondition and the code is correct then the if (n==0) {return 1;}
}
postcondition to the method will hold. Postconditions else {return n*fact(n-1);} Rewrite this program with a more efficient fact
are written as comments at the top of the method } method.
after the word post.
25 26 27
}
Program Input cod Output d o c Summary
reverse(); reverse() A routine that calls itself is called recursive.
ch ='c' Methods can be recursive, programs cannot.
Recursive methods that produce a single result are just like
Lecture 3 : Arrays and For Loops
reverse()
void reverse(){
ch='o'
Haskell functions. Lecturer : Susan Eisenbach
char ch; Void methods are used when the same operation is to be
reverse()
performed on different data and the result wanted is
ch = read(); ch='d' output on the screen. For extra material read parts of chapters 3
if (ch != '\n'){ reverse() In order that the repetition may be finite, within every and 6 of Java Software Solutions.
ch='\n' recursive method there must appear a terminating condition
reverse();
print(ch) to guard the recursive call and a progression to This is the 3rd lecture on Java in which arrays
print(ch); print(ch) distinguish one call from another. and for loops are examined.
} Switch statements are used rather than conditionals when
print(ch)
there are several choices based on an integer or character.
} 37 38 Susan Eisenbach 39
{
elements of an array are all of the same type and
referred to by an index get space to String[] words = new String[5];
arrays can be one or more dimensional hold 10 doubles
its an array
arrays are called vectors and matrices by non-
computing people the name of the array is vec
“Tom”
comparison with Haskell lists “is”
– every element can be accessed with equal ease each element is a double “not”
– multi-dimensional arrays are easy to access “my”
“friend”
40 41 42
Examples of array variable Arrays can be initialised at
declarations declaration Getting the size of an array
To get the size(no. of elements) of an array, you write
arrayname.length
int[][]mat = new int[5][4]; String[] names = {“Bradley","Eisenbach", The length of the array is determined by the number
of values provided between { }.
"Gillies","Field", for example if
"Hodkinson"}; boolean[] answers = {true, false,
double[] vector = {0.1, 1.2, 0.0, 34.6, true, true, false};
This is an then
-3.0, 34.1, 0.0,
array of arrays answers.length is 5
0.4, 0.8, 0.1}; Note that length is not a method and so does not
have ( ). It is built into Java.
Once created, the size of the array cannot change.
43 44 The length of the array must be specified when it is 45
created.
Tracing the execution of some When trying to understand what some piece of Java When trying to understand what some piece of Java
code does you hand execute all the code working out code does you hand execute all the code working out
code what the values of the variables are: what the values of the variables are:
mean total i v[0] v[1] v[2] v[3] v[4] void main(){ mean total i v[0] v[1] v[2] v[3] v[4]
void main(){ 1 0 3 1 5 double[] vec = {1,0,3,1,5}; 1 0 3 1 5
double[] vec = {1,0,3,1,5}; println( mean(vec) );
When trying to understand what some println( mean(vec) ); } 0
piece of Haskell code does, you use }
double mean(double[] v){
double mean(double[] v){
int i;
1 0
rewrites: int i; double total = 0.0;
1 1
4 2
fact 4 = 4*fact 3 = 4*3*fact 2 =
double total = 0.0; for (int i =0;i<v.length;i++)
for (int i =0;i<v.length;i++) { 5 3
4*3*2*fact 1 = 4*3*2*1= 24 { total = total + v[i];
10 4
total = total + v[i]; };
}; return total/v.length; 5
return total/v.length; } 2
}
52 53 54
What is the value of names.length?
For each i, what is the value of names[i].length?
Nested for loops Summary
a 2-dimensional array requires 2 for loops to traverse
it: void main(){ Arrays are data structures suitable for problems
int sum(int[ ][ ] m){
String[][] students ={
{"BSc", "Homer", "Marge", "Bart", "Lisa", "Maggie"}, dealing with large quantities of identically typed
//post: returns the sum of the elements of m {"MSci", "Moss", "Jen", "Roy"},
{"BEng", "Peter", "Lois", "Meg", "Brian", "Stewie",},
data where similar operations need to be
int theSum = 0; {"MEng", “Harry", "Adam", "Ros", "Malcolm","Zafar","Connie"} performed on every element.
for (int i = 0; i<m.length; i++){ };
for (int j = 0; j<m[i].length; j++){ printNames( students ); Elements of an array are accessible through their
index values. Arrays using a single index are
}
theSum = theSum + m[i][j]; void printNames(String[ ][ ] names){
} for (int i = 0; i < names.length; i++) {
print(names[i][0] + ": "); called vectors, those using n indices are n-
dimensional arrays. A two dimensional array is
} for (int j = 1; j < names[i].length; j++) {
return theSum; print(names[i][j] + " ");
} } really an array of arrays, a 3-dim., an array of
arrays of arrays, etc.
println();
an n-dimensional array requires n for loops to traverse }
}
If int mat[50][100] is passed to sum, what is the
value of m.length? For each i, what is the value of
55 56 57
m[i].length?
61 } 62 63
Write a predicate isDiagonal that takes as Write a predicate hasFullRow that takes as Write a predicate hasFullCol that takes as
arguments an X or O and a board and returns true iff arguments an X or O and a board and returns true arguments an X or O and a board and returns true
one of the diagonals is filled with the piece. iff one of the rows is filled with the piece. iff one of the columns is filled with the piece.
boolean isDiagonal(char ch, char[ ][ ] b){ X X O boolean hasFullCol(char ch, char[][] b){ X X O
boolean hasFullRow(char ch, char[ ][ ] b){ assert: ch='X' || ch='O';
assert (ch='X' || ch='O'); assert (ch='X' || ch='O'); O O X
O O X boolean found;
return b[0][0]== ch && boolean found; for (int c = 0; c < 3; c++){
X X
O
X X
for (int r = 0; r < 3; r++){ O
b[1][1]== ch && found = true;
b[2][2]== ch || found = true; for (int r = 0; r < 3; r++){
for (int c = 0; c < 3; c++){ found = found && b[r][c] == ch;
b[0][2]== ch && found = found && b[r][c] == ch;
b[1][1]== ch && X X O }
}
if (found) {return true;}
b[2][0]== ch; O if (found) {return true;} }
} } return false;
X
O
return false; }
}
64 65 66
Put them together to produce a How do you get which square
Exercises to do yourself: predicate isWinner the next player wants?
You could (mouse) click on the square on the screen and the
Write the predicate hasFullCol that takes as coordinates could be converted into the appropriate
arguments an X or O and a board and returns boolean isWinner(char ch, char[][] b){
noughts and crosses index.
true iff one of the columns is filled with the assert: ch='X' || ch='O'; This requires very sophisticated input routines.
piece using only one loop. return isDiagonal(ch,b) || Simpler would be to read in from the keyboard chess
notation for the square and then convert it to the
Rewrite the code in the slides with hasFullRow(ch,b) ||
appropriate array indices.
the board as a one dimensional array. hasFullCol(ch,b); So if a user wants the middle square, it is b2 or 2b
How much harder is it to write the X X O } X X X and the bottom lefthand corner is c1 or 1c a X X O
X X O
predicates? O O X O O X
O O X O O O b
X X X X
O O
X X
O
c
67 68 1 2 369
You need to know if the character the Convert the input characters into numbers
user typed in is for a row or a column that can be used for array indices Arguments to methods
Write a predicate IsRow which takes as an We have been passing arguments to methods.
argument a character and returns true iff the Write a method convert that takes a character
argument is an 'a', a 'b' or a 'c'. that is a valid row or column and returns the Java's argument passing is slightly more
appropriate number to use for the row index or restrictive than Haskell's – you can pass
boolean isRow(char c){ column index. So if '2' is passed as an argument anything to a Java method, except another
return 'a' <= c && c <= 'c'; to convert it returns 1. method.
} int convert(char c){ In Java methods, arguments are passed by
Write a predicate IsCol which takes as an assert (isRow(c) || isCol(c)); value. When invoked, the method receives the
argument a character and returns true iff the if (c=='1' || c=='a') {return 0;} value of the variable passed in, creates a local
argument is an '1', a '2' or a '3'. copy, works on it and then discards it when the
boolean isCol(char c){
if (c=='2' || c=='b') {return 1;} method is left.
return '1' <= c && c <= '3';
return 2; This means that a method cannot change the
} 70
}
71
value of its arguments. 72
What happens when you pass a variable to a What happens when you pass a variable to a When a method is called the runtime system of
method and change its value within the method? method and change its value within the method? any language holds method data in a stack
void main(){ void main(){
int a = 1; int a = 1;
a=1 a=1
int b = 2;
int b = 2; println("a & b = " + a + b); b=2 b=2
println("a & b = " + a + b); swap(a,b); println println
swap(a,b); println("after swap " + a + b);
} temp = 1 temp = 1
println("after swap " + a + b); void swap(int a, int b){
} //post: this method does very little a=2 a=2
void swap(int a, int b){ int temp = a;
b=1 pop
push Aa = 21 , b = 12 , temp = 1 b=1
//post: this method does very little a = b;
b = temp; println push println
int temp = a; Aa = 1, b = 2
println("inside swap " + a + b);
a = b; } a & b = 1 2 println println
b = temp; inside swap 2 1
println("inside swap " + a + b); 73 after swap 1 2 74 75
}
Tuples
When you want to group many of the same type of
int fact(int n){ element together in Haskell you use a list, in Java you
assert (n>= 0&& n <17); use an array.
//post: computes n! You access elements in a list through the head and an
int f = 1; Lecture 5 : Classes array by index (position of element).
Sometimes you want to group a few items of (possibly)
for (int i=n; i>0; i--){ different types together.
f = f*i; Lecturer : Susan Eisenbach In Haskell you would use a tuple. The position of the
} For extra material look at chapters 2 and 4 of Java piece of data would tell you what it was.
return f; Software Solutions. In Haskell you wanted to hold an applicant's name
}
This is the 5th lecture in which classes and objects are followed by the A level points of the top 3 A levels you
introduced. might say:
– type Applicant = ([Char], Int, Int, Int)
– and you would know that the name was the first element of an
82 Susan Eisenbach 83 Applicant. 84
In Java there are classes Using variables of type Applicant Draw a diagram to understand
Applicant me;
Classes can be used like tuples, (although they are Applicant you;
class Applicant{
Draw a diagram of an Applicant.
String name;
much more powerful as you will see later in the course) me.name = "Susan"; int grade1; Susan 60 40 0
Classes contain fields and fields are accessed by name me.grade1 = 60; int grade2; name grade1 grade2 grade3
(not position like tuples) me.grade2 = 40; int grade3;
class Applicant{
me.grade3 = 0; } Rewrite the class declaration for Applicant
String name;
Classes can be passed as arguments and returned from methods so the three grades are held in an array. Draw
int grade1;
boolean areSame(Applicant a1, Applicant a2) a diagram of your new class.
int grade2;
int grade3; What is the difference between the two statements? class Applicant{
– println(me.name + (me.grade1 + me.grade2 + Shakil 120 120 120 String name;
} Susan100 0 1 2
me.grade3)); int[] grades =
Classes are types, (like Haskell types). You create the name grades new int[3];
– println(me.name + me.grade1 + me.grade2 +
type with the class declaration and then you need to
}
declare variables of the type you have created. 85 me.grade3); Susan60400 86 87
Coord getMove(){
Coord move;
getMove in Java
Declare getMove What is the algorithm for getMove? char c1; char c2;
c1 = readChar();
c2 = readChar();
getMove takes no arguments (it reads its c1 = readChar() if (isRow(c1) && isCol(c2)){
c2 = readChar()
move.row = convert(c1);
inputs from the keyboard) and returns a move.col = convert(c2);
Coord. Coord getMove() if isRow(c1) && isCol(c2) return move;
move.row = convert(c1) }
What local variables are needed by getMove? move.col = convert(c2)
else{
-two variables to hold the input characters if (isCol(c1) && isRow(c2)){
return move move.row = convert(c2);
char c1, c2; else if isCol(c1) && isRow(c2) move.col = convert(c1);
move.row = convert(c2)
return move;
-a variable to hold the coordinates of the move to be }
returned move.col = convert(c1) else{
for input and a column for output. playGame the whole game goes here
100 101 102
main k k Do you want to play again(y/n)? k
Primitive values Primitive values
ints, doubles, booleans, Strings, and What happens is the bit pattern that is the
chars are primitive. value at the storage location called a is
Java has many other number types that are compared with the bit pattern at the storage
Lecture 6 : Objects also primitive. location called b.
Primitive variables are names for storage If they are identical the value of the
locations that contain the values of the expression is true otherwise it is false.
Lecturer : Susan Eisenbach variables.
For extra material read chapter 4 of Java Software What happens when during the execution of int a = 3;
Solutions.
your program checking the expression a==b int b = 4; 0…0…011 == 0…0…100 ???
This is the 6th lecture in which primitive types and where a and b are both ints is reached?
objects are introduced. The last tutorial question is also a==b?
gone over. a b
Java provides arraycopy for Arguments to methods – repeat What happens when you pass a variable to a
copying arrays. of earlier slides (reminder) method and change its value within the method?
void main(){
arraycopy takes source and copies it to We have been passing arguments to methods.
int a = 1;
destination Java's argument passing is slightly more int b = 2;
What gets printed? restrictive than Haskell's – you can pass println("a & b = " + a + b);
int[ ] v1 = {1,1,1,1};
anything to a Java method, except another swap(a,b);
method. println("after swap " + a + b);
int[ ] v2 = {2,2,2,2};
arraycopy(v1,v2); In Java methods, arguments are passed by }
v1[0] = 33; value. When invoked, the method receives the void swap(int a, int b){
for (int i=0; i < v2.length; i++){ value of the variable passed in, creates a local //post: this method does very little
print(v2[i]);
copy, works on it and then discards it when the int temp = a;
method is left. a = b;
}
This means that a method cannot change the b = temp;
1111 112
value of its arguments. 113 println("inside swap " + a + b); 114
}
What happens when you pass a variable to a What happens when you pass an object to What happens when you pass an object to
method and change its value within the method? a method and alter the object? a method and alter the object? 21 12
void main(){
int a = 1;
a=1 void main(){ void main(){
int b = 2; int[ ] p = {1,2}; int[ ] p = {1,2};
println("a & b = " + a + b); b=2 println("p[0] & p[1] = " + p[0] + p[1]); p=
swap(a,b); println println("p[0] & p[1] = " + p[0] + p[1]); swap(p); println
println("after swap " + a + b); swap(p); println("after swap " + p[0] + p[1]);
} temp = 1 temp = 1
println("after swap " + p[0] + p[1]); }
void swap(int a, int b){ void swap(int[ ] p){
//post: this method does very little a=2 } p[0] = 2
int temp = p[0];
int temp = a; void swap(int[ ] p){
b=1 p[0] = p[1]; p[1] = 1
a = b; int temp = p[0];
b = temp; println p[1] = temp; println
println("inside swap " + a + b);
p[0] = p[1]; println("inside swap " + p[0] + p[1]);
} a & b = 1 2 println p[1] = temp; } p[0] & p[1] = 1 2 println
inside swap 2 1 println("inside swap " + p[0] + p[1]); inside swap 2 1
after swap 1 2 115 } 116 after swap 2 1 117
end. The way an array or class is accessed is via its address println("p[0] & p[1] = " + p[0] + " " + p[1]);
in the heap also called a pointer. }
However the object lives in the heap and there If an object has not been allocated space then the
void change1(int[ ] p){
is no such thing as a local heap. address will be a special one called a Null Pointer.
int[ ] q = {99,999};
p = q;
Any alterations to the heap that happen during If you try to access an object that has not yet been println("inside change1: p[0] & p[1] = "+p[0]+" "+p[1]);
allocated some space then you will get a
the execution of a method are permanent. NullPointerException.
}
void change2(int[ ] p){
A NullPointerException means you tried to access an p[0] = 1000;
object, which did not exist. println("inside change2: p[0] & p[1] = "+p[0]+" "+ p[1]);
118 119 } 120
Answer: Consider an array of classes How do we write Thing[]initThings?
p[0] & p[1] = 10 20 class Thing{ Within initThings we need first to create an array.
int value = 0; Thing[] tt = new Thing[5];
If tt just held integers then each array element would
char answer = 'y';
inside change1: p[0] & p[1] = 99 999
contain a 0.
}
p[0] & p[1] = 10 20 void main(){ But since each array element holds an object it needs
printThings(initThings()); to contain the address of the object.
inside change1: p[0] & p[1] = 1000 20 As none of the objects have yet been given addresses
}
p[0] & p[1] = 1000 20 then each array element contains the special null
void printThings( Thing[] tt){ address which is normally shown with the symbol you
can see below:
Why do you get this output? for (int i = 0; i < tt.length; i++){
println("value = "+tt[i].value+" answer = "+tt[i].answer);
}
}
Execute the program in step mode and check the 0 ‘y’ return tt;
array values at each for loop iteration. }
void main() { One of the most useful things you can do switch ( today ){
for(Days d = Days.SUN; with an enumerated type is use it for a case MON :{}
case TUES :{}
d != null; switch variable. case WED :{}
d = enumSucc(d)) In switch cases, you must remember not case THURS :{work(); break;}
{ Cannot use < or > on to put the type-name as a prefix for the case FRI :{play(); break;}
println(d); an enumerated type,
constants. case SAT :{}
just == and !=. case SUN :{doNothing();}
}
}
}
The hardest problem Declaring coins How do you solve the problem?
Given an amount it will be necessary to convert Write the declaration (header) for a You need to create a local (just in the method)
it into the (fewest) coins needed to make up array money to return from the method
that amount. So we need a method that does
method called coins which takes as containing the different numbers of coins.
the following: arguments the amount (assume it is > 0) You need a local variable whatsLeft that
– 3 {1,1,0,0,0,0,0,0} and the values of the coins. Include your contains the amount you haven't yet put into
– 65 {0,0,1,1,0,1,0,0}
– 48 {1,1,1,0,2,0,0,0} , etc.
pre and post conditions. money.
To do this the array of values is also required, walk over the array values from right to left
int[] coins(int n, int[] values)
since we need to know the value of each of the assert (n > 0); money[i] = whatsLeft / values[i]
coins. //post: the fewest coins whose values sum to whatsLeft = whatsLeft % values[i]
// equal n is returned return money
142 143 144
What if you want to be able to
In Java do the converse of coins? Write the method sum in Java
{ Declare a method sum which takes as an argument an int sum(int[] money, int[] values){
int money = new int [8]; array money which contains the number of each of the //post: the monetary value of m is returned
int whatsLeft = n; coins and which returns the sum of the coins. You will
also need to pass values as an argument in order to
int total = 0;
for (int i = money.length-1; i>=0; i--){
money[i] = whatsLeft / values[i]; calculate the sum. Include any pre or post conditions. for (int i = 0; i<money.length; i++){
whatsLeft = whatsLeft % values[i]; int sum(int[] money, int[] values) total = total + money[i]*values[i];
} //post: the monetary value of m is returned }
return money; What is the algorithm for the body of the method? return total;
} total = 0 }
walk over the array money (from left to right)
total = total + money[i]*values[i]
145
return total 146 147
Example stubs for testing the main program Calling the stubs Debugging complete code
Expression readExpression(){ class Expression {
Expression e; int first = 0; when a program goes wrong you need:
char op;
e.first = 2; int sec = 0; – what code was being executed
e.op = '*'; } – what data was being used
e.sec = 21;
void main(){ code being insert debugging code
return e;
}
String notCalculable = "cannot calculate"; tested need to produce a trace
Expression expr; main program entered
boolean isCalculable( Expression e ) { expr = readExpression();
return true; if ( isCalculable(expr) ) {println("= " + evaluate( expr ) );}
isCalculable entered
} else {println( notCalculable );} evaluate entered
}
Expression readExpression(){stub code goes here} <crash>
int evaluate( Expression e ) { boolean isCalculable( Expression e ) {stub code goes here}
assert (isCalculable(e)); int evaluate( Expression e ) {stub code goes here}
return 42; 208 209 210
}
Permanent tracing code Debugging data Summary
use a boolean constant at the top of the code Need to print out values of possible offending Test throughout program development to ease finding
bugs.
boolean tracing = true; variables
Use test harnesses and stubs to find bugs in methods.
at the start of each method foo include: Use another boolean constant for this: Test a program against its requirements.
if (tracing) {println( "foo entered" );}
boolean debug = true ; Test with typical data, then at limits then outside the
at the end of each void method include: specification.
Insert code where it might be needed:
if (tracing) {println( "foo exited" );} If a program does not work properly it needs to be
¿ Why don't non-void methods get this code as well? if debug {println("ch = " + ch);} debugged. Insert debugging code to find the source of
Write methods to print out classes: the error. Do this systematically.
When you don't want to see the trace you change the
value of tracing to false. Trace your program by hand. Time spent this way will
void printExpression(Expression e) be less than the time spent sitting at the machine
looking for bugs.
211 212 213
User defined types User defined types are not enough Many Haskell functions are polymorphic
Java cannot provide every data structure that fst :: ( a, b ) -> a Pair index
is needed by every programmer. Although user defined types are useful
Java lets you create new data structures using something like Haskell’s polymorphism is fst(3,”Hello”) of 3
important so that the user defined types do
its classes. not have to contain the type of the elements. Note that the type of fst involves two
When accessing elements of these user The latest Java now has generic types which type variables
defined data structures methods are used. are similar to polymorphic types.
since pair elements can be of any type
So instead of getting elements with x[i], like So now in Java it is possible to define lists,
arrays or x.i like fields in classes, the trees, etc which can be used for holding values
programmer has to write methods to get items of any type such as ints, chars or whatever is
from the user defined data structures. required by the program.
type in Java:
Pair<String> twoStrings; Pair<String,String> twoStrings;
twoStrings.a = "hello"; twoStrings.a = "hello";
class Pair<T>{ twoStrings.b = "world"; twoStrings.b = "world";
T a;
type variable declaration println(twoStrings.a);
T b; Pair<int,char> intChar;
Pair<int> twoInts; intChar.a = 3;
}
twoInts.a = 3; intChar.b = 'x';
To declare a pair of two elements of (possibly) twoInts.b = 4; println(intChar.b);
different types in Java: }
println(twoInts.a); }
return p.a; <T> Stack push (Stack<T> s, T item) {//code goes here Write push(numS,3) to push 3 onto numS
} and top(opS) is the top operator on the
} //post top(result)=item operator stack.
returns something of the first generic type
<T> Stack pop(Stack<T> s) {//code goes here
226 assert (isEmpty(stack)) :"cannot pop an empty stack"; 227 228
}
Using a stack calculate: Example: calculate 1+3*4 /2 =
if there is another item (operand or operator)
We have not said how the actual stack is implemented if it is an operand if there is another item (operand or operator)
as we have not shown the data declarations. Perhaps push it onto the numberStack, skip over the item,
if it is an operand
our stacks will be implemented as arrays – but they calculate the rest of the expression
push it onto the numberStack, Skip over the item,
You only use the access methods that need to be calculate the rest of the expression calculate the rest of the expression
written: isEmpty, empty, pop, push and top. else pop the top two operands and the top operator, 12
3
6 /* else pop the top two operands and the top op,
evaluate the expression formed,
Use is independent of the implementation of the evaluate the expression formed,
push the result onto the numberStack,
71 + push the result onto the numberStack,
method. calculate the rest of the expression
calculate the rest of the expression