You are currently browsing the category archive for the ‘Uncategorized’ category.

Pressing on with SICP, these sections look at how we can combine simple expressions to make more complicated ones.

1.1.3 Evaluating combinations

To evaluate a combination, the interpreter performs the following steps:

  1. Evaluate the subexpressions
  2. Apply the procedure that is the value of the leftmost subexpression to the arguments that are the values of the other subexpressions

The evaluation procedure is recursive in nature – one of its steps is to invoke itself. The base case for this recursion comes when the interpreter encounters a primitive element. We handle the base cases by defining:

  1. The values of numerals are the numbers that they represent
  2. The values of built-in operators are the sequence of machine instructions that carry out the corresponding operations
  3. The values of other names are the objects associated with them in the environment.

It is key to notice the role of the environment: simply writing (+ x y) makes no sense without specifying the environment that provides a meaning for the symbols x and y (or even +).

This evaluation rule doesn’t handle definitions. For example, the line of code (define x 3) does not apply the procedure define to the values of the arguments x and 3 – rather it assigns the value 3 to the variable x.

Such exceptions are called special forms. We will meet more of them shortly.

1.1.4 Compound procedures

We’ve identified some of the elements that must appear in any powerful programming language:

  1. Numbers and arithmetic operations: primitive expressions
  2. Nesting S-expressions: a means of combination
  3. Definitions that associate names with values: a means of abstraction

Procedure definitions provide a more powerful abstraction, whereby a compound operation can be given a name and then referred to as if it were a primitive. For example, we could define a procedure that squares a number:

> (define (square x) (* x x))

This is a compound procedure that has been given the name square, which evaluates to the procedure ‘multiply the argument x by itself’.

The general form of a procedure definition is

(define (<name> <formal parameters>) <body>)

I’m following the convention of SICP that text inside angle brackets is a placeholder for some real code. The is a symbol to be associated with the new procedure in the current environment. The give names to the arguments of the procedure, and the is the description of the procedure.

Having defined square, we can use it:

> (square 14)
196

We can also use it as a building block in other procedure definitions, for example:

> (define (sum-of-squares x y)
    (+ (square x) (square y)))
> (sum-of-squares 3 4)
25

Compound procedures are used in the same way as primitive procedures – you can’t tell by looking at the definition of sum-of-squares whether square is built in, or defined as a compound procedure.

Advertisements

Suppose you have a set of cards labeled 1, 2, …, N. You shuffle them, and start dealing out the deck. As you deal it out, you keep a card if it’s the highest card you’ve seen so far. Otherwise you discard it.

You always end up keeping the first card; you keep the second only if its higher than the first, the third only if its higher than both of the previous two, etc.

On average, how many cards do you keep once you’ve dealt through the entire pack?