CS61B, lecture #2 6/20/00. P. N. Hilfinger with Modifications by B. Chen Handouts: Homework 1 Reading assignments: For today: Friesen pp. 30-64. Reader: Model for Memory, Names, and Types For tomorrow: Friesen pp. 64-73, 262-274 For Thursday: Friesen pp. 75-102, 235-249 Administrative: 0. The instructor, although not visibly present, can still be reached via e-mail: brudno@cs.berkeley.edu for any and all questions. 1. To re-iterate, we will not allow more than 35 students in ANY section. Section 102 is especially overbooked. If you're officially enrolled in any particular TeleBears section, you're in that section. There's a lot of space available in sections 105 and 106 at 5pm and 6pm respectively. If you cannot switch to another section where there is space, I will have to drop you from the course. 2. Everyone MUST get an account, login, and answer the set of questions that are presented at the beginning of the session. Otherwise, we will assume you are not in the course. To check to see if you are registered, use the command 'check-register'. To change registration information if it is inaccurate, use the command 're-register'. 3. Go to discussion today and make sure you get in a tutorial. Labs are now optional. 4. HW 0 will be graded based on how well you follow directions. Please go back and make sure that you followed them properly. If you already sent the e-mail, odds are you did not. Actual Material ------ -------- The Scheme program that corresponds to our little ``Hello World!'' example is (define (Hello.main args) (ask System.out 'println (string-append "Hello, world! Did I hear you say \"" (vector-ref args 0) "\"?"))) ----------------------------------- The Java Equivalent (from Lecture 1) public class Hello { static public void main (String[] args) { System.out.println("Hello, world! Did I hear you say \"" + args[0] + "\"?"); } } The correspondences between Java and Scheme illustrated here are Java CS61A Scheme 1. class Foo {...} (define-class Foo ...) 2. static T0 Glorp(T1 a1, T2 a2...) (define (Foo.Glorp a1 a2) { body } body ) Assuming that this appears inside class Foo. The T's denote TYPES. They do not appear in Scheme because you can't in general identify a single type of data that is returned by a function or passed as an argument. 3. "A string" "A string" 4. oneString + anotherString (string-append oneString anotherString) 5. Foo.bar(x) (ask Foo 'bar x) where Foo denotes an object Java Data Values ---- ---- ------ Every Java value has a (at least one) `type,' just as in Scheme, some things were atoms, some were pairs, and so forth. The Java language is structured in such a way that one can tell, for every expression (or subexpression), what type(s) of values it can have. For example, in the method int f(String a, int y) { int x = Integer.parseInt(a) + 6; return x * y; } I know that when f is called, it must have two arguments, the first must be a String, the second must be an int, and that f will return an int. Furthermore, inside the {}'s, I know that x will contain only int's, a will contain only Strings, y will contain only ints, x*y will yield an int, and so forth. We say Java is `statically typed.' There are two categories of type: primitive (which are numeric values) and reference (which are pointers to objects). The primitive types are boolean, the integer types byte, short, char, int, and long, and the floating-point (rational) types float and double. In contrast to Scheme, they have limited ranges. For example, the range of type int is integers representable in 31 binary digits, plus a sign. On the numeric values, Java gives us a bunch of pre-defined operations: +, -, *, /, % (remainder), & (bitwise and), | (bitwise or), ~ (bitwise complement), ^ (bitwise exclusive or). In addition, x << y is x multiplied by 2 to the y, x >> y is x multiplied by 2 to the -y and rounded down, and x>>>y will take some explaining. More on all of these at a later time. For booleans, we have & or && (and), | or || (or), and ! (not). The 'doubled' operators && and || are special "short-circuit" operators. E1 && E2 evaluates only E1 if E1 turns out to be false, and E1 || E2 evaluates only E1 if E1 turns out to be true. Finally, the expression C ? E1 : E2 acts like Scheme's expression (if C E1 E2). Because Java uses infix notation (operator between operands) rather than Scheme's bracketed prefix notation (operator before operands, surrounded by parentheses), there is an amibiguity in interpreting something like a-b-c (is it (a-b)-c or is it a-(b-c)?) or a+b*c. Like most so-called `algebraic languages,' Java has a set of `grouping rules' that assign a `precedence' to the operators. The reference values (all other values) all point to things. When I write: SomeReferenceType x; I mean that ``x either contains the value null or it contains a pointer to a SomeReferenceType object.'' Initially, x contains null (although for some reason, the Java people think it is naughty to depend on that). We'll see below how to get new reference objects of one kind. Some Basic Java Expressions and Classes ---- ----- ---- ----------- --- ------- * /* .... */ To denote a comment in Java, you surround the comment with /* and */ To comment an entire line, begin the line with // The latter is similar to the scheme style of commenting by using the semi-colon. { // this is a comment int x = 0; /* so are these lines */ int y = 1; } * { ... } When there is more than one statement in SomeAction, we turn the multiple statements into one by surrounding them in { ... }. You may have noticed that Java statements that don't end in `}' end in `;'. In the sequence { Something }; there are two statements: ``{ Something }'' and the empty statement ``;'' * if (SomeTest) DoOneThing Same as Scheme's (if SomeTest DoOneThing). * if (SomeTest) DoOneThing else DoAnother Same as Scheme's (if SomeTest DoOneThing DoAnother) * while (SomeTest) SomeAction This is equivalent to the Scheme code (define (aloop) (if SomeTest (begin SomeAction (aloop)))) (aloop) All tests in Java must yield boolean values. * for (SomeType SomeVar = SomeValue; SomeTest; SomeAction) DoSomething This is the same as { SomeType SomeVar; SomeVar = SomeValue; while (SomeTest) { DoSomething; SomeAction; } } If you leave off the ``SomeType'', it's the same as SomeVar = SomeValue; while (SomeTest) { DoSomething; SomeAction; } * return X; In Scheme, one writes (define (foo ...) ... ValueToReturn ) to return a value from a function. In Java, we write ... SomeType foo(...) { ... return ValueToReturn; } except that we can do it from anywhere in the program. * int N = getArgument(args); This is like (let ((N (getArguments args))) rest-of-program ) in Scheme, except that, as you can see, we don't put the rest of the program in it. Instead, the `scope' of this declaration is everything up the end of the enclosing {...}. It is equivalent to int N; N = getArgument(args); (the `=' is like set! in Scheme). As a matter of style, I usually use the combined form when (as here) I don't intend N to change. The `int' means that N can only contain values of type int (a restricted range of integers). * Something += 1; (Read ``Something plus and becomes 1'') Same as Something = Something + 1; There's a whole family of these guys: *=, /=, -=, %=, &=, |=, ^=, <<=, >>=, >>>=. * args.length == 1 args.length gives the length (number of elements) in SomeArray. The first is numbered 0, and the last is numbered SomeArray.length-1. The == operator means ``equals'' (to distinguish it from `=', which is read ``becomes'', ``gets'', or ``is assigned''). * try { Something } catch (SomeKindOfException e) { SomeResponse } Well, this is a little complicated. It means ``try to evaluate Something, and if it causes SomeKindOfException to happen (we say ``to be thrown''), then execute SomeResponse. We'll get into exceptions at a later time. For now, you'll just see examples. The reason I have it here is that it is possible the programmer gave me bogus input that doesn't look like an integer. When that happens, Integer.parseInt (a function that converts strings of digits into integers) is said to ``throw a NumberFormatException exception.'' * System, Math These are standard classes. Their full names are java.lang.System and java.lang.Math. I didn't have to write the full names because all the classes in java.lang are automatically visible to everyone. * Math.min, Math.sqrt Functions for computing the miniumum of two numbers and the square root of a number. Java Basic Control & Data Structures: an Example ---- ----- ------- - ---- ----------- -- ------- Here is a Java program for printing prime numbers from 2 up to any limit: public class Primes0 { /* Print all prime numbers up to and including ARGS[0], which must be a valid positive integer. */ public static void main(String[] args) { int N = getArgument(args); int i = 2; while (i <= N) { if (isPrime(i)) { System.out.print(i); System.out.print(" "); } i += 1; } System.out.println(); } /* Extract the argument value to the program from the command-line arguments ARGS. */ static int getArgument(String[] args) { if (args.length == 1) { try { return Integer.parseInt(args[0]); } catch (NumberFormatException e) { } } System.err.println("Usage: java Primes N"); System.err.println(" where N is an integer."); System.exit(1); return 0; } /* True iff N is prime. */ static boolean isPrime(int N) { if (N < 2) return false; else { int limit = (int) Math.sqrt((double) N); for (int i = 2; i <= limit; i += 1) if (N % i == 0) return false; return true; } } } Performance ----------- Well, this is all very well, but it takes 2300 seconds on my 200MHz Pentium-based computer to compute the primes up to 10,000,000. We can speed things up a little by such tricks as skipping even numbers, but it is even better to use the Sieve of Eratosthenes. When doing this by hand, we write out all the numbers we're interested in: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Now, find the first number that you haven't reported yet (2), report it (announce it's prime) and then `cross off' every 2nd number: 2 3 X 5 X 7 X 9 X 11 X 13 X 15 X 17 X 19 X 21 X 23 X 25 X 27 Now repeat: find the first remaining number that you haven't reported yet (3), report it and then cross off every 3rd number (count the `X's as if they're still numbers; it doesn't hurt to cross them off again). 2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X 25 X X Repeat for 5: 2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X Once we get up to the square root of the maximum number we're interested in, we're done (why?). We can speed things up further by noticing that after reporting k, there's never any point in crossing off numbers before k*k (why?). Alas! It's rather clumsy to have a sequence of things that can be either numbers or `X's. But we needn't give up: it's the thought that counts. Let's REPRESENT our this sequence of numbers as a sequence of true's and false's, with a false at every crossed-off point: t t f t f t f f f t f t f f f t f t f f f t f f f f (Why don't I need to keep around the actual numbers?). In Java, an array is something that is pointed to by a `reference' value. When I write boolean[] X; I'm saying that X will contain pointers (arrows) to arrays of booleans (true/falses). I'm NOT saying to make X point to one of those things just yet. A New Java Expression - --- ---- ---------- * new SomeType[SomeValue] This is like make-vector in Scheme. It returns a pointer to a new array with SomeValue slots, each of which contains a SomeType. The Improved Primes Program --- -------- ------ ------- Here is a Java program to implement the Sieve of Eratosthenes. It computes the primes to 10,000,000 in 230 seconds on the same system as for the first program. public class Primes1 { public static void main(String[] args) { int i; int N = getArgument(args); boolean[] isPrime = makePrimeSieve(N); for (i = 2; i <= N; i += 1) if (isPrime[i]) { System.out.print(i); System.out.print(" "); } System.out.println(); } ... /* getArgument is the same as before */ /* Return an array of size N+1 for which element number k is true iff k is prime. Requires that N >= 0. */ static boolean[] makePrimeSieve(int N) { boolean[] sieve = new boolean[N+1]; sieve[0] = sieve[1] = false; for (int i = 2; i <= N; i += 1) sieve[i] = true; int limit = (int) Math.sqrt(N) + 1; for (int i = 2; i <= limit; i += 1) { if (sieve[i]) for (int j = i*i; j <= N; j += i) sieve[j] = false; } return sieve; } }