Chris Taylor

Math, coding, finance, geekery

# SICP 1.1 – Exercises

July 7, 2011 in Coding, Programming, SICP | Tags: coding, exercises, lisp, programming, scheme, sicp

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

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.

### About me

Proto-hacker, ex-mathematician and aspiring flaneur. Now living in London and making my living from algorithmic trading.

### Twitter

• RT @Betfairpoker: Can anyone truly enjoy watching a man wearing shorts if you know deep down that he probably only owns one house? 2 months ago

## 2 comments

I would have done it like this (in Emacs-Lisp):

(defun square (num)
(* num num))

(defun largest (n nums)
(last (sort nums ‘<) n))

(defun sum-square-largest-2 (&rest nums)
(apply '+ (mapcar 'square (largest 2 nums))))

This creates something that is modular, easy to understand, and easily generalized. Sure, sorting the whole list might be a little inefficient, but that is a premature optimization. You could always replace largest with an efficient selection algorithm if you needed.

Pretty-printed version on gist.

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 1, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9083746075630188, "perplexity_flag": "middle"}