Tagged: Structure and Interpretation of Computer Programs

Who has been given the cash changing problem?


Some class, somewhere, has obviously been given the recursive money changing problem as a piece of work, because I have had several hundred visits in the last week from people seeking to get a grip on it.

Here’s the best solution, either buy Structure and Interpretation of Computer Programs or simply read it for free online.

Related articles

An idea I saw on normblog


The panel at the public launch of the Euston M...

Image via Wikipedia

Norman Geras is a great man. He’s a social, not a computer, scientist, and this year I have been mainly reading computer books. Still, here’s an idea I have pinched off his website (he got it from here). Match the prompts to books you have read in the last year – in my case mainly computer books.

One time on holiday: Understanding the Linux Virtual Memory Manager

Weekends at my house are: Code Complete

My neighbour is: Programming Pearls

My boss is: The Mythical Man Month

My superhero secret identity is: The Annotated Turing

You wouldn’t like me when I’m angry because: Mussolini’s Italy

I’d win a gold medal in: The Little Schemer

I’d pay good money for: Structure and Interpretation of Computer Programs

If I were Prime Minister I would: Groovy in Action

When I don’t have good books, I: P, NP, and NP-Completeness

Loud talkers at the cinema should be: Albion’s Fatal Tree

Related articles

My first R program


Having used Groovy (which makes the scripting environment feel familiar) and some Scheme (via Structure and Interpretation of Computer Programs), R does feel completely alien, but it still feels like a steep learning curve.

But here’s my short script -

unpatched <- read.csv("~/unpatched.txt")
unpatchcons <- transform(unpatched, realm=realm*60 + reals)
attach(unpatchcons)
linelog<-lm(realm~size)
plot(size, realm, log="y")
abline(reg=linelog, untf=TRUE, col="blue",lty=3)
detach(unpatchcons)

And here’s the graph (of Linux kernel compile times) it generates – the blue line is obviously a very bad fit!

Linux kernel compile times

Related articles

Something more on Fibonacci numbers


Pascal triangle Fibonacci

Image via Wikipedia

My earlier blog about the Fibonacci series gets a lot of hits, so I thought I would write something more, as clearly there is interest.

Once again this is from “Structure and Interpretation of Computer Programs” (available for free here electronically):

Let \psi = (1 - \sqrt{5})/2 and \phi = (1 + \sqrt{5}/2) . Then Fib(n) = (\phi^n - \psi^n)/\sqrt{5} .

So Fib(1) = (\frac{1}{2} +\frac{\sqrt{5}}{2} - \frac{1}{2} + \frac{\sqrt{5}}{2})/\sqrt{5} = 1 .

(1)Fib(n) = (\phi^n - \psi^n)/\sqrt{5} = Fib(n - 1) + Fib(n - 2)

(2) Then Fib(n -1) + Fib( n - 2) = \frac{\phi^{n-1} - \psi^{n-1}}{\sqrt{5}} + \frac{\phi^{n-2} - \psi^{n-2}}{\sqrt{5}}

(3) Simplifying (2) Fib(n) = \frac{\phi^{n-1} - \psi^{n-1} + \phi^{n-2} - \psi^{n-2}}{\sqrt{5}}

(4) Simplifying further – from (1): \phi^n - \psi^n = \phi^{n-1} - \psi^{n-1} + \phi^{n-2} - \psi^{n-2}

(5) \phi^n - \psi^n = \phi^{n - 2}(\phi + 1) -\psi^{n- 2} - \psi^{n - 1}

(6) We know that \phi^2 = (\phi + 1) so we can restate (5) as \phi^n - \psi^n = \phi^n - \psi^{n - 2} - \psi^{n - 1}

So (7) \psi^n = \psi^{n - 2} + \psi^{n - 1}

But \psi^2 = \psi + 1 also and (7) can be restated as \psi^n = \psi^{n-2}(\psi + 1) = \psi^{n-2}\psi^2 = \psi^n

In other words, Fib(n) = (\phi^n - \psi^n)/\sqrt{5} .

Related Articles

The lambda calculus and closures in Groovy


Alonzo Church (1903–1995)

Alonzo Church: Image via Wikipedia

No sooner had I written about the lambda calculus and Structure and Interpretation of Computer Programs than I sat in a lecture on closures in Groovy and was presented with a structure like this (which multiplies two numbers, in this case 3 and 4):

a simple closure in Groovy

Which immediately reminded me of one of Alonzo Church‘s formulations of lambdas – eg:

A lambda calculus representation of a formula

More to come…

Related Articles

Coming up… the lambda calculus


An example of a DFA state diagram

Image via Wikipedia

Another thing that The Annotated Turing taught me is what all those lambdas that I have seen over the last 25 years were about, or at least it introduced me to what they were about.

So I have just ordered a copy of Structure and Interpretation of Computer Programs: and I can guess that some blog posts will eventually follow.

Oh no. Maybe I am turning into a LISP hacker – having finally reached the age that all these guys were when I first became aware of them (older, actually).

Related Articles