You are currently browsing the tag archive for the ‘programming’ tag.

The first exercise is merely to evaluate some Lisp expressions manually, and then check them in the interpreter. Easy and not too interesting, but I did say that I’d do every exercise, so I guess I’ll plough ahead.

This is good time to talk about the interpreter I’m using. I initially toyed with downloading the MIT Scheme interpreter, which is a minimalist product that’s designed to be used alongside this course. I also thought about downloading Emacs – you can get implementations with a built-in Lisp interpreter. But I’ve been getting along quite happily with a combination of Vim and TextMate (for Mac OS X) for the past few months, and I’m not sure that learning a new text editor is necessary right now. I also wanted to do some more advanced coding in Lisp (what’s the point of learning a new language if I’m not going to use it?) so I wanted something a bit meatier than MIT Scheme.

DrRacket

DrRacket

I eventually settled on Racket, a bells-and-whistles implementation of Scheme that includes a lot of extra features out of the box – lots of nice data structures, the ability to create GUIs and manipulate graphics, and lots more. It comes with its own interpreter, DrRacket, which is functional and pretty easy to use. A nice touch is that you can load any definitions file into the interpreter to give you a whole load of pre-defined functions – and if the first line of the definitions file is #lang <language-name> then you will only use the features of that language. For example, the first line of the definitions file I’m using for this project is #lang scheme so I don’t have access to all the funky procedures defined in Racket – just the core Scheme language.

On with the exercises.

Exercise 1.1

What is the result printed by the interpreter in response to each of the following expressions?

> 10 
10

Numerals have a value equal to the number they represent.

> (+ 5 3 4)
12

This is equivalent to 5 + 3 + 4. Note that the + procedure can take multiple arguments. I haven’t learned how to define a function with a variable number of arguments yet, but hopefully I will soon!

> (- 9 1)
8

This is equivalent to 9 – 1.

> (/ 6 2)
3

Equivalent to 6 / 2. Note that we get an integer result.

> (+ (* 2 4) (- 4 6))
6

Equivalent to (2 * 4) + (4 – 6) = 8 + (-2). Note that there is no need for operator precedence in Scheme, because we always include the parentheses! I wonder if a syntax for Scheme could be defined that allowed you to leave out parentheses when the meaning was clear, and had rules of operator precedence instead. For example, the K programming language that I use at work has simple right-to-left order of evaluation. This can lead to very code and lets you easily write one-line expressions that are very powerful, but has many gotchas: for example, 2*4+5 evaluates to 18 in K, rather than 13.

> (define a 3)

Whether or not define statements return a value is implementation-dependent. My interpreter doesn’t give a return value. However, we have now bound the value 3 to the variable a.

> (define b (+ a 1))

Again, there is no return value, but we have bound the value of (+ a 1) to the variable b, so that b now has the value 4.

> (+ a b (* a b))
19

This is equivalent to a + b + (a * b) where a = 3 and b = 4.

> (if (and (> b a) (< b (* a b)))
      b
      a)
4

This procedure says “if (b > a) and (b < a * b) then return b, else return a”, which becomes “if (4 > 3) and (4 < 12) then return 4, else return 3” so it returns 4.

> (+ 2 (if (> b a) b a))
6

First evaluate the if statement. It says “if (b > a) return b, else return a” which becomes (by substitution) “if 4 > 3 then return 4, else return 3”, so it returns 4. We then evaluate (+ 2 4), which returns 6.

> (* (cond ((> a b) a)
           ((< a b) b)
           (else -1))
     (+ a 1))
16

We first evaluate the cond statement. It evaluate to 4, since the first predicate is false but the second one is true. The second argument (+ a 1) evaluates to 4 also, and finally (* 4 4) evaluates to 16.

Exercise 1.2

Translate the following expression into prefix form:

\dfrac{5 + 4 + (2 - (3 - (6 + 4/5)))}{3(6 - 2)(2 - 7)}

I reckon we have:

> (/ (+ 5
        4
        (- 2
           (- 3
              (+ 6
                 (/ 4 5)))))
     (* 3
        (- 6 2)
        (- 2 7)))
-37/150

That return value was a surprise to me! I had assumed that when applying the division operator to two integers, Scheme would either perform integer division (like Java) or return a floating point number (like Python). Apparently it has a built-in rational data type. Which is nice.

Exercise 1.3

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

Here’s a pretty ugly answer, using the built-in min function:

> (define (f a b c)
    (- (+ (* a a) (* b b) (* c c))
       (* (min a b c) (min a b c))))

Why is it ugly? Well, it needlessly applies min twice, and it does four multiplications, two additions and a subtraction, when all that’s needed is one addition and two multiplications. How about:

> (define (g a b c)
    (cond ((and (<= a b)
                (<= a c)) (+ (* b b) (* c c)))
          ((<= b c) (+ (* a a) (* c c)))
          (else (+ (* a a) (* b b)))))

This looks uglier, but it’s more efficient: it never performs more than two multiplications and one addition, and never more than three comparisons (the minimum possible, since you have to sort the arguments so that you know which is the smallest, and this takes three comparisons in the worst case. If anyone has a prettier and efficient solution (perhaps one that works for arbitrary lists of arguments?) then I’d like to see it.

We’re going to introduce a simple model for how the interpreter evaluates expression that you type in, and then go on to look at an important feature of Lisp (well, an important feature of any programming language…): conditionals.

1.1.5 The substitution model for procedure application

A model for how the interpreter applies primitive procedures to arguments is as follows:

To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

Let’s illustrate this by evaluating

(sum-of-squares 3 4)

which expands to

(+ (square 3) (square 4))

Now, (square 3) evaluates to 9 and (square 4) evaluates to 16, so we have

(+ 9 16)

and finally we get the result

25

This is called the substitution model for procedure application. This is not how the interpreter really works, but it is a simple model that captures the spirit.

Applicative order and normal order

We said that the interpreter first evaluates the operator and operands, and then applies the procedure to the resulting arguments. This is not the only way to evaluate compound procedures. An alternative model does not evaluate any expressions until their results are needed. Instead, it substitutes expressions for parameters until it obtains an expression involving only primitives, and then performs the whole evaluation.

For example, (sum-of-squares 3 4) would be evaluated first to

(+ (square 3) (square 4))

and then to

(+ (* 3 3) (* 4 4))

and now that we only have primitives, we can begin evaluating the whole expression:

(+ 9 16)

and finally

25

This is called normal-order evaluation, as opposed to applicative-order evaluation which is what the compiler actually uses. Normal-order evaluation is less efficient (since you can end up evaluating the same expression multiple times) and becomes problematic when we leave the realm of procedures that can be modeled by substitution.

1.1.6 Conditional expressions and predicates

There is a special construct in Lisp for doing case analysis, called cond which stands for “conditional”. It is used as follows:

> (define (abs x)
    (cond ((> x 0) x)
          ((= x 0) 0)
          ((< x 0) (- x))))

The general form of a conditional expression is

(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>))

i.e. it consists of the symbol cond followed by pairs of expressions in parentheses:

(<p> <e>)

called clauses. The first expression in each pair must be a predicate, i.e. an expression that evaluates to true or false.

Conditional expressions are evaluated as follows. The predicate <p1> is evaluated first. If its value is false then <p2> is evaluated, and so on. This continues until a predicate is found whose value is true, in which case the interpreter returns the value of the appropriate consequent <e> as the value of the cond expression. If none of the predicates evaluate to true, then the value of the cond is undefined.

There is a special symbol else which can be used in place of the final predicate. This causes the cond to return the value of the final expression <e>. We could also write the absolute value procedure as:

> (define (abs x)
    (cond ((< x 0) (- x))
          (else x)))

There is also the special form if, a restricted form of conditional that can be used when there are exactly two mutually exclusive cases. This gives another way to write the absolute value procedure:

> (define (abs x)
    (if (< x 0)
        (- x)
        x))

The general form of an if expression is

(if <predicate> <consequent> <alternative>)

To evaluate the expression, the interpreter first evaluates the <predicate> part. If it is true, then it returns the value of <consequent> as the value of the if, otherwise it returns the value of <alternative>. It is important to realise that only one of the <consequent> and the <alternative> are ever evaluated.

In addition to primitive predicates like and = there are also logical composition operators, enabling us to construct compound predicates. The three most common are

(and <e1> ... <en>)

which returns false if any of the <e> evaluate to false, and otherwise returns true,

(or <e1> ... <en>)

which returns true if any of the <e> evaluate to true, and otherwise returns false, and

(not <e>)

which returns true if <e> evaluates to false, and false if evaluates to true.

As an example of use, we could define a predicate to test whether one number is greater than or equal to another by

> (define (>= x y)
    (not (< x y)))

and we can use it:

> (>= 10 2)
#t
> (>= 2 10)
#f

Next I’ll look at some of the exercises.

Out of a desire to (i) learn a functionalStructure and Interpretation of Computer Programs programming language, and (ii) generally become a better programmer, I’ve decided to work my way through Abelson and Sussman’s Structure and Interpretation of Computer Programs. It’s a bit of a beast, but I’ve read a chunk of it already and its style appears to me. I’ve also been intending to learn a dialect of Lisp for a while, and this seems like a good opportunity.

This is the book which forms the core of the borderline-legendary MIT course 6.001, which provides as good an introduction to the foundations of computer programming as is available anywhere in the world. It will be difficult, but rigorous.

The idea is that I’ll read every word, and do all of the programming exercises. As I finish eash section, I’ll post what I’ve learnt here, together with the source code I used to solve the exercises, and anything else I think will be useful.

I fully expect it to take me a long time (fitting it in around a day job will be tricky) but I’m feeling confident. If anyone has read it (or even better, is reading it at the moment) I’d love to hear from you.

I was linked to a collection of Edsger Dijkstra’s writings today, and spent an interested half hour reading some of them. Djikstra was known for composing his manuscripts in longhand, using a fountain pen. He would then make a dozen or so photocopies, and mail them out to people he knew to be interested in his work. They would then be further disseminated by those people, and so on, until his work had reached a wide audience. Each article was coded with his initials EWD, followed by a three or four digit number — they thus became known as EWDs in the computer science world.

The most interesting article I read today was EWD831, whose full title is Why numbering should start as zero. Djikstra argues persuasively that counting should start from zero, and thus that all arrays should be indexed beginning from zero. This runs counter to the natural intuition (and to what we are taught at school) that counting begins at 1.

In brief, Dijkstra’s argument runs like this. There are four possibilities for notating the range of numbers 1, …, 10 without using ellipsis notation, which can be ambiguous:

  1. 1 ≤ i < 11
  2. 0 < i ≤ 10
  3. 0 < i < 11
  4. 1 ≤ i ≤ 10

There are several desirable properties that we might want our system of notation to have. For example:

  • (a) the difference between the bounds is equal to the number of terms in the sequence
  • (b) two ranges are adjacent if the upper bound of one is equal to the lower bound of the other.

Both 1 and 2 satisfy these properties, but 3 and 4 don’t. If we want to use our notation to specify a range of natural numbers, then it seems sensible to ask for the following two properties:

  • (c) the lower bound is a natural number
  • (d) the upper bound is a natural number, even when defining the empty sequence

Property (c) is only satisfied by 1 and 4 and property (d) is only satisfied by 1 and 3 So we see that it is only notation 1 that satisfied all of the properties we desire.

Now we move on to the question of whether we should start indexing at 0 or at 1. This is simply an issue of aesthetics. If we want to describe the range of an array with N entries, then by starting at 0 we would write the range as 0 ≤ i < N, whereas if we start indexing at 1 then it is written as 1 ≤ i < N+1, which is significantly more ugly. So we see that we should start indexing at 0. Note that programming languages such as C, Java and Python all follow this convention, as do most widely adopted languages. The only commonly used languages I can think of that don’t use it are Fortran and R.