Structure and Interpretation of Computer Programs is a classic, must read computer science book. It focuses on the core ideas of computer science that can be applied to all languages. Like my Thinking in Java posts, I am going to use this blog to keep track of my progress as I read through the book again. SICP uses Scheme to illustrate the ideas, but I will mostly use Common Lisp, and maybe even a little Python just to show the differences.

Chapter: Everything is an Object

Exercise 4: (1) Turn the DataOnly code fragments into a program that compiles and runs.

Again, not completely sure what they're after, but here is one that works:

public class Excercise4 {
    public static void main(String[] args) {
        DataOnly data = new DataOnly();
        
        data.i = 20;
        data.d = 1.23;
        data.b = false;
        
        System.out.println(data.i);
        System.out.println(data.d);
        System.out.println(data.b);
    }

}

class DataOnly {
    int i;
    double d;
    boolean b;
}

In Lisp:

(defclass data-only ()
  ((i :accessor the-int :initform 20)
   (d :accessor the-double :initform 1.23)
   (b :accessor the-bool :initform nil)))

(setf data (make-instance 'data-only))
(print (list (the-int data)
             (the-double data)
             (the-bool data)))

In Python:

class DataOnly:
    i = 20
    d = 1.23
    b = False

data = DataOnly()

print data.i
print data.d
print data.b

Chapter: Everything is an Object

Exercise 3: (1) Find the code fragments involving ATypeName and turn them into a program that compiles and runs.

Not exactly sure what they're looking for here, but here's a simple program in Java:

public class Exercise3 {
    public static void main(String[] args) {
        ATypeName x = new ATypeName();
        System.out.println(x.i);
    }
}

class ATypeName {
    int i = 5;    
}

Chapter: Everything is an Object

Exercise 2: (1) Following the HelloDate.java example in this chapter, create a “hello, world” program that simply displays that statement. You need only a single method in your class (the “main” one that gets executed when the program starts). Remember to make it static and to include the argument list, even though you don’t use the argument list. Compile the program with javac and run it using java. If you are using a different development environment than the JDK, learn how to compile and run programs in that environment.

The classic Hello World program in Java:

public class Exercise2 {
    public static void main(String[] args) {
        System.out.println("Hello Blog Readers!");
    }
}

In Lisp:

(print "Hello Blog Readers!")

In Python:

print "Hello Blog Readers!"

Chapter: Everything is an Object

Exercise 1: (2) Create a class containing an int and a char that are not initialized, and print their values to verify that Java performs default initialization.

Java code:

public class Exercise1 {
    static int i;
    static char c;

    public static void main(String[] args) {
        
        System.out.println("Int: " + i);
        System.out.println("Char:" + c);
    }
}

Result:

Int: 0
Char:

Ints default to 0 and chars default to null. Note that you will get a complier error if you declare the variables within a method and try to use them without initializing them.

Bruce Eckel's Thinking in Java is considered one of the best books for learning Java and Object Oriented programming. To help keep my Java skills sharp, I will try to work through many of the problems, and also compare the Java solutions to solutions written in my favorite languages, Lisp and Python, where applicable. I hope that keeping a blog of my progress will motivate me to finish.

The Society for Neuroscience recently released an article about the effects sleep deprivation has on the human brain. When the human brain loses focus, the frontal and parietal regions of the brain compensate by increasing attention. However, sleep-deprived people showed less activity in these areas of the brain, which lead to longer attention lapses because the brain enters a sleep-like state and becomes less responsive to sensory stimuli. So, if you plan on doing tasks that involve critical thinking, adequate rest is essential.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

One way to find the prime factors is to make a function that starts at two, tests to see if it's a factor, and iterate upwards. Then, when a factor is found, save it and use recursion to call the function with the number divided by the factor as the argument.

For example, let's say we want to find the prime factors of 100. We have our function, foo(n) with n = 100, that starts at 2, iterates up, and stops when a factor of 100 is found. Since 2 divides into 100, it stops at the first iteration, saves 2, and calls foo(100/2). We can do this because there can't be any factors above 50, so we won't bother checking them, which vastly increases our efficiency. Proceeding through foo, it returns the numbers 2, 2, 5, 5. The largest number of the results is the answer.

In Common Lisp:

(defun problem-3 ()
 (reduce #'max
     (labels ((prime-factors (num)
                (unless (<= num 1)
                  (do ((x 2 (1+ x)))
                        ((zerop (mod num x))
                         (cons x
                                  (prime-factors (/ num x))))))))
       (prime-factors 600851475143))))

The above lisp code can be cryptic for people unfamiliar with the language. Think of labels as just defining the local function prime-factors. Prime-factors takes a number, tests to see if it's greater than one, then if it is proceeds into the do-loop. The do-loop starts with x = 2 and increases x by 1 with every iteration. It stops when the remainder of num / x = 0. When it stops, it outputs a list of x and the result of prime-factors (num / x). This recursions stops when the number = 1. The reduce #'max statement finds the maximum value of the list returned by prime-factors.


In Python:

def flatten(L):
    if type(L) != type([]): return [L]
    if L == []: return L
    return flatten(L[0]) + flatten(L[1:])

def primeFactors(num):
    if num <= 1:
        return []
    x = 2
    while x <= num:
        if num % x == 0:
            return [x] + [primeFactors(num / x)]
        x += 1

def problem3():
    return max(flatten(primeFactors(600851475143)))

This is an interesting article about the lifestyle of a 114-year old man. Apparently, he had cycled every day until he was 102, has a Mediterranean diet (he lives in Spain), and lives in a mild climate. Researchers analyzed his genetics but were unable to discover any genetic mutations that contribute to his longevity.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

A brute force method would be to iterate through all the Fibonacci numbers under four million, and for each test if the number is even, then add it to the sum if it is even. But if we look at the sequence of numbers, we can see a pattern of even numbers.

term 0 1 2 3 4 5 6 7 8 9 10 11 12
value 1 1 2 3 5 8 13 21 34 55 89 144

Every third Fibonacci number is even. If Fib(n) equals the value of the nth Fibonacci term, we can add every third term to find the answer.

Let's start with Fib(2). Fib(2) = Fib(1) + Fib(0). By definition, we know Fib(0) and Fib(1) both equal one, so Fib(2) equals two. To get the next even term, we need to add 3 to n: Fib(5) = Fib(4) + Fib(3). Ignoring the term/value table above, we can calculate Fib(3) because we know the values of Fib(2) and Fib(1). Then, we can calculate Fib(4) because we know the values of Fib(3) and Fib(2). And finally, we can calculate the value of Fib(5) because we know Fib(4) and Fib(3).

The solution in lisp:

(defun problem-2 (limit)
  (do* ((sum 0 (+ sum n))
           (n-2 1 (+ n-1 n))
           (n-1 1 (+ n n-2))
           (n 2 (+ n-2 n-1)))
       ((< limit n) sum)))

The '*' after the 'do' is necessary so the terms are evaluated in sequence rather than in parallel.

In python:

def problem2(limit):
 sum = 0
 n2, n1, n = 1, 1, 2
 while n < limit:
   sum += n
   n2 = n1 + n
   n1 = n2 + n
   n = n1 + n2
 print sum