MzScheme in Aquamacs Emacs

Aquamacs Emacs has built in support for Scheme, but not for MzScheme, which is one of the versions of Scheme of PLT DrScheme. You envoke it by M-x run-scheme, which searches for scheme in the path.

I have put MzScheme in the path, and I could rename it to scheme, but that would break DrScheme. The solution is to create a symbolic link (symlink) of mzscheme and rename that symlink into scheme. I could do that in Terminal with ln -s mzscheme scheme, but there is also a way to do that in Mac OS X, with the freeware application SymbolicLinker, wich appears in the contextual menu of Finder.

That makes sense, because the reason to use Aquamacs Emacs was to stay in the GUI of Mac OS X, and this SymbolicLinker contextual menu continues using this strategy.

Pondering about programming

Sometimes it is good to take some distance from what you're doing, so you can set your priorities for the near future.

Wat is programming, actually?

Seems to be a silly question, because you'd think that programming is about producing code, but it's not.

I suggest you read Teach Yourself Programming in Ten Years, by Peter Norvig. Most noteworthy programs are written as team efforts, and if you want to become a good programmer, you need to be able to work in a team, sometimes as an experienced leader and sometimes as a novice to the software project (in order to give orders, you have to be able to follow orders as well).

A good programmer has good interpersonal skills and can work in teams. Interactions between programmers are perhaps more important than the code they write.

Writing good code should be the goal

Unfortunately, the coding community has the reputation of writing bad, bug-ridden code, that needs constant updating and lots of support to and feedback from the end-users (which explains why good customer support is such a large chuck in the total costs of software development). Also, people tend to own a part of a project, do poor documentation, then run away from projects and leave the team with undocumented, buggy code, which has to be fixed by other people. There are a lot of bad coding teams out there. Not necessarily because the team members are bad coders, but because the team's organization, well um, sucks.

So how to spot good coding practices? Read The Joel Test: 12 Steps to Better Code and learn.

Concepts, Techniques, and Models of Computer Programming

I found another good resource for learning how to write computer programs, called "Concepts, Techniques, and Models of Computer Programming", by Peter Van Roy and Seif Haridi. It uses declarative programming and distributive computing as a programming paradigm, and its programming language of choice is Mozart-Oz.

One could see this as a successor of "Structure and Interpretation of Computer Programs" by Harold Abelson and Gerald Jay Sussman, which used functional programming as a programming paradigm, and Scheme as the programming language of choice.

Both have their values as instructional books, because they learn you to see computer programming in new ways you never imagined existed before.

I will be concentrating on the SICP book for now, but it is good to know that there are more excellent books to learn how to write programs using your human intelligence and imagination, instead of copying and pasting what others have done before you. Nothing wrong with the latter, but I don't aspire to become a script kiddie, or even a code monkey. I want to design programs.

Aquamacs Emacs

I was trying to get to grips with GNU Emacs, when I came across a Mac OS X specific equivalent, called Aquamacs. Well, it isn't really an equivalent, but, if I understood correctly, it is a graphical user interface (GUI) shell around GNU Emacs. It is meant to keep you in the spirit of GUI, not having to switch gears to a command-line-interpreter-state of mind.

• Aquamacs website

Thinking in C

On Mindview.net there is an excellent C foundation course in Shockwave Flash format that you can download from here as a ZIP archive for off-the-Net viewing. It isn't a full introductory course, but rather concentrating on the parts of C you'll need to better understand Java or C++.

Mindview also has courses in C++ and Java, called Thinking in Java and Thinking in C++, so this Thinking in C course could be seen as an introductory course for these other, more advanced courses. If I understood correctly, the old versions of these two courses can be downloaded for free, but if you want the most recent versions, you have to buy the printed copies, which seems reasonable to me.

I have done the first introductory chapter and it seems to be excellent for those who have little programming experience. However, I don't recommend it for the absolute newbies in programming, because it might be a little too steep in the learning curve for those. You need to be aware of some basic concepts of program development, and how your system works on the command line.

For those absolute newbies to programming, I recommend a site like the platform-independent Programming 101.

For how the command line works, I advice to visit:

• Command-line reference (Windows)
• Learning the Mac OS X Terminal (Mac OS X)
• An introduction to the Linux command line (Linux)

I realize that these might not be the best links for newbies (especially the Windows link). If anyone has suggestions, feel free to put it in a comment.

Alternative to MIT course

At UC Berkeley there is an alternative to the MIT course "Structure and Interpretation of Computer Programs". The webcast page can be found here. The video is only streaming (Real Media), but the audio can be downloaded as a (MP3) podcast through iTunes.

There is a UCB Scheme, called STk, which has versions for Windows, Linux and Mac OS X.

In Mac OS X (which I happen to use), you'll need to run from a X11 terminal window, which needs to be pre-installed. For versions of Mac OS X before 10.4 (Tiger), you need to download XDarwin, if you haven't done so already. For OS X 10.4 and higher, there is a X system—X11 and Xorg—on the install disk, which should be used instead of the download from XDarwin.org. If you have X11 available in your /Applications/ folder, you already have X installed.

NB: While the podcast is convenient, it is not very useful to understand the lessons. You really need to watch the video stream, and perhaps use the podcast as a preview, to get a quick overview of the lecture before paying attention to details.

SICP - 1.1 The Elements of Programming

Exercise 1.1.

Below is a sequence of expressions. What is the result printed by the interpreter in response to each expression? Assume that the sequence is to be evaluated in the order in which it is presented.

10
(+ 5 3 4)
(- 9 1)
(/ 6 2)
(+ (* 2 4) (- 4 6))
(define a 3)
(define b (+ a 1))
(+ a b (* a b))
(= a b)
(if (and (> b a) (< b (* a b)))
    b
    a)
(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
(+ 2 (if (> b a) b a))
(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))

Solution

10
12
8
3
19
4
16
6
16

Exercise 1.2.

Translate the following expression into prefix form

5 + ⅓ + (2 - (3 - (6 + ⅓)))
————————————————————————————
      3(6 - 2)(3 - 7)

Solution

(/
 (+ 5
    1/3
    (- 2
       (- 3
          (+ 6 1/3))))
 (* 3
    (- 6 2)
    (- 3 7)))

Exercise 1.3.

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

Solution

(define (sum-squares-largest-two a b c)
  (if (> a b)
      (if (> b c)
          (+ (sq a) (sq b))
          (+ (sq a) (sq c)))
      (if (> a c)
          (+ (sq a) (sq b))
          (+ (sq b) (sq c)))))
(define (sq x)
  (* x x))

Exercise 1.4.

Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

Solution

If b is larger than zero, the + operation is used to combine a and b, otherwise the - operation is used. The latter operation negates the negative (or zero) value of b, and, in effect, adds the absolute value of b to a.

Exercise 1.5.

Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

Then he evaluates the expression

(test 0 (p))

What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)

Solution

In the case of normal-order evaluation, (test 0 (p)) is evaluated as follows:

(test 0 (p))

(if (= 0 0)
    0
    (p)

(if (= 0 0)
    0
    (p)

(if #t
    0
    (p)

0

In the applicative order, (test 0 (p)) is evaluated as follows:

(test 0 (p))

(test 0 (p))

(test 0 ((p)))

(test 0 (((p))))

...

The interpreter keeps adding parentheses around (p) until infinity, and there will never be a result printed, because it will take forever to evaluate the expression (test 0 (p)).

Exercise 1.6.

Alyssa P. Hacker doesn't see why if needs to be provided as a special form. "Why can't I just define it as an ordinary procedure in terms of cond?" she asks. Alyssa's friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

Eva demonstrates the program for Alyssa:

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0

Delighted, Alyssa uses new-if to rewrite the square-root program:

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x)
                     x)))

What happens when Alyssa attempts to use this to compute square roots? Explain.

Solution

The program goes into an endless loop, because it keeps evaluating (sqrt-iter (improve guess x) x) with new values for guess, adding a new-if in each iteration after the existing new-if.

The reason that this happens is because if is a keyword and

(if predicate consequent alternative)

is a special case, instead of a regular combination or a procedure (like new-if). This means the order in which terms are evaluated in the if special form is different than in the new-if procedure.

The special form if evaluates the predicate first and if it returns a non-false value (everything else than #f), it evaluates the consequence, never evaluating the alternative. This means that if there is a base case, the recursion will end at some point. In the original definition there is such a base case, namely when the absolute value of the difference between the square of the guess and the number value the sqrt-iter definition consumes is less than a certain constant value.

When the new-if procedure is used, the three argument expressions of the procedure call are evaluated before new-if is applied to the evaluated expressions. In order to evaluate the third argument expression, which is a recurvive call to sqrt-iter, the new-if of that recursive call has to be evaluated first. Of course, this recursive call also has a third argument expression, with the same consequence of calling new-if for that successive recursive call, and so on. The result is that new-if calls are being added to the evaluation process and there is never going to be a base case that ends this. The program gets into an endless loop until the user halt it.

Exercise 1.7.

The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?

Solution

For x < 1e-6, the square root of x is always smaller than 0.001, so the absolute value of the difference between the square of guess and x will always be smaller than 0.001, and the result of good-enough? will always be a true value.

In real computers, if x is sufficiently large, the number of decimal places will be too small to hold enough precision to let guess² close in on x.

(define (sqrt x)
  (sqrt-iter 2.0 1.0 x))

(define (sqrt-iter old-guess guess x)
  (if (good-enough? old-guess guess)
      guess
      (sqrt-iter guess (improve guess x)
                 x)))

(define (good-enough? old-guess guess)
  (<
   (if (< old-guess guess)
       (/ guess old-guess)
       (/ old-guess guess))
   1.001))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

Exercise 1.8.

Newton's method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a better approximation is given by the value

x/y² + 2y
—————————
    3

Use this formula to implement a cube-root procedure analogous to the square-root procedure. (In section 1.3.4 we will see how to implement Newton's method in general as an abstraction of these square-root and cube-root procedures.)

Solution

(define (cube-root x)
  (cube-root-iter 2.0 1.0 x))

(define (cube-root-iter old-guess guess x)
  (if (good-enough? old-guess guess)
      guess
      (cube-root-iter guess (improve guess x)
                 x)))

(define (good-enough? old-guess guess)
  (<
   (if (< old-guess guess)
       (/ guess old-guess)
       (/ old-guess guess))
   1.001))

(define (improve guess x)
  (/ (+ (/ x (sqr guess)) (* 2 guess)) 3))