1.1.1: Syntax & Semantics

Chapter 1.1 mingles syntax with the basic functional/applicative idea of ‘evaluating and substituting’. 1 evaluates to 1, 1 + 1 evaluates to 2, 1 + 1 / 2 evaluates to 2 / 2 which evaluates to 2, and so on.

It’s something of an unobvious idea—when you think about it, it’s not the same as equaling, but it doesn’t exactly seem like the normal idea of an algorithm. Evaluation is kind of a do-while loop: ‘while the result of evaluation is different from the evaluated thing, keep evaluating.’ One expects a fixed number of steps. Think of a child doing chores: you don’t tell her to clean each part of the living room until it’s clean, you tell her to clean first the cat throwup over in the corner, then take care of the overfull garbage bag, then vacuum, then sweep and finally you can go play.

Iteration is more natural and intuitive in a sense. I don’t think I’ve ever seen any youngster express things in a functional or recursive form very naturally. They have tremendous trouble when their math classes start touching on algebra and functions and evaluation.

(define (second-order x) (-
                          (+
                           (* 3 (expt x 2))
                           (* 14 x))
                          5))

secondOrder x = 3*x^2 + 14*x - 5

quadraticRoot a b c = ((-b) + sqrt (b^2 - 4*a*c)) / 2*a

(define (quadratic-root a b c) (/ (+ (- b)
                                     (sqrt (-
                                            (expt b 2)
                                            (* 4 a c))))
                                  (* a 2)))

1.1.2: Variables Don’t

To Lisp’s credit, the rest of the core syntax is really marvelously simple.

Consider the define function. It’s basically a = operator. (define two 2), (define item "foobar"), etc. But notice how regular it is! It’s always just (define x y). You type it into the prompt and all is well.

Consider the comparable situation in Haskell: in GHCi you have the choice between let x = y, and x <- y; and then in a source file you could also do ...where x = y or even x = y! If you want to understand fully when let is appropriate, or when to do <-, or when a bald mathematical definition is appropriate, you need to have at least some knowledge of monads & their do-syntax, the peculiarities of GHCi (conceptually, you’re inside an IO monad, and not at the top-level of a file), and so on. There’re good reasons for all this (such as controlling side-effects), but how do you explain them to a beginner? For that matter, the value of controlling side-effects doesn’t become obvious for a while, and the experienced imperative programmer might never appreciate it.

1.1.4: The Evil That Functions Do…

Defining functions is similarly simple & pleasant. We go (define (square x) (* x x)) and that’s that. The opening keyword, a function name & a argument, and then the actual math.

This is actually worse than Haskell. There’s no way to define a square pointlessly like we can in Haskell (square = join (*)) and certainly we can’t employ a lambda as flexibly (square = \x -> x * x)—what one would expect to work just doesn’t seem to work (at least, (define (square) (lambda (x) (* x x))) doesn’t even parse). For that matter, the most basic square function just looks better in Haskell: square x = x*x. You basically can’t get more readable than that. Yes, it’s harder to parse, but still…

Well, the syntax is not the important part. The important part is that we now have a way to package up manipulations at the prompt—instead of defining a variable and manually typing in (* variable variable) every time, we give the procedure a name and can reuse it. Note how we’re ascending in abstraction: first we divided between literals like 1 and variables which point to literals like an x, and now we’re abstracting ourselves! Our monkey-punching at the keyboard is being replaced; the operator of a prompt need not be human. We’re almost at a loop here—the prompt generates things which are fed to the prompt… But we’re not there yet. We need to understand what’s going on better. by seeing how functions are substitutable as well.

1.1.5: About That Elegant Model…

Turns out it wasn’t so simple or accurate at all. Sorry about that:

The purpose of the substitution is to help us think about procedure application, not to provide a description of how the interpreter really works. Typical interpreters do not evaluate procedure applications by manipulating the text of a procedure to substitute values for the formal parameters. In practice, the ‘substitution’ is accomplished by using a local environment for the formal parameters. We will discuss this more fully in chapters 3 and 4 when we examine the implementation of an interpreter in detail.³

But if ‘how a computer works’ were really so simple, would this really be the ‘Structure and Interpretation of Computer Programs’? It just means we can look forward to still more fun:

Over the course of this book, we will present a sequence of increasingly elaborate models of how interpreters work, culminating with a complete implementation of an interpreter and compiler in chapter 5. The substitution model is only the first of these models—a way to get started thinking formally about the evaluation process. In general, when modeling phenomena in science and engineering, we begin with simplified, incomplete models. As we examine things in greater detail, these simple models become inadequate and must be replaced by more refined models. The substitution model is no exception. In particular, when we address in chapter 3 the use of procedures with ‘mutable data’, we will see that the substitution model breaks down and must be replaced by a more complicated model of procedure application.

(define (p) (p))

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

1.1.6 Maybe Yes, Maybe No

Now we set our hand to conditionals. Lisp differs markedly from Haskell in that its basic conditional is not the if-then-else, but this cond structure. Cond takes a list of pairs: the first item is a test, and the second is the value to return. So (cond ((= 0 0) 0) ((= 1 2) 1)) would evaluate to 0. Further, cond returns the first item to be true, so even if we changed it to read ((= 1 1) 1), it’d still return 0.

The Haskeller immediately objects that Haskell has a perfectly suitable work-alike—guards. We can almost transcribe from Lisp cond to Haskell guards:

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))
        (true (error "error"))))

becomes

abs x
    | x > 0 = x
    | x == 0 = 0
    | x < 0 = -x
    | otherwise = error "error"

(define (ifthenelse test thn els)
        (cond (test thn)
              (true els)))

abs x = if (x > 0) then x else if (x == 0) then 0 else if (x < 0) then -x else error "error"

cond :: [(Bool, a)] -> a
cond [] = error "all results were false"
cond xs = if head (fst x) then head (snd x) else cond (tail xs)

10
-> 10

(+ 5 3 4)
-> 12

(- 9 1)
-> 8

(/ 6 2)
-> 3

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

(define a 3)
-> <a>

(define b (+ a 1))
-> **

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

(= a b)
-> false

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

(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
-> 16

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

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

10

5+3+4

9-1

6/2

(2*4) + (4-6)

let a = 3

let b = a + 1

a + b + (a*b)

a==b

if ((b>a) && (b < a*b)) then b else a

if a=4 then 6 else if b=4 then (6+7+a) else 25

2 + (if (b > a) then b else a)

a+1 * if (a > b) then a else if (a < b) then b else -1

(define (tri x y z)
  (cond
    ((and (>= x y) (>= y z)) (+ (* x x) (* y y)))
    ((and (>= x y) (<= y z)) (+ (* x x) (* z z)))
    (true                    (+ (* y y) (* z z)))
   ))

tri x y z
    | x >= y && y >= z = x*x + y*y
    | x >= y && y <= z = x*x + z*z
    | otherwise        = y*y + z*z

import Data.List (sort)
tri2 :: Int -> Int -> Int -> Int
tri2 x y z = let a = sort [x,y,z] in (a!!1)^2 + (a!!2)^2

testWrong :: IO ()
testWrong = quickCheck(\x y z -> tri x y z == tri2 x y z)
→ *** Failed! Falsifiable (after 7 tests and 7 shrinks): 0 1 -1

tri3 :: Int -> Int -> Int -> Int
tri3 x y z
    | x<=y && x<=z = y*y + z*z
    | z<=y && z<=x = y*y + x*x
    | otherwise = x*x + z*z -- y<=x && y<=z

testRight :: IO ()
testRight = quickCheck(\x y z -> tri2 x y z == tri3 x y z)
→ +++ OK, passed 100 tests.

(define (tri x y z)
  (cond
    ((and (<= x y) (<= x z)) (+ (* y y) (* z z)))
    ((and (<= z y) (<= z x)) (+ (* y y) (* x x)))
    (true                    (+ (* x x) (* z z)))
    ))

1.1.7: …of Beautiful and Practical Design

Now this is an interesting section. It’s an interesting exercise, and even more interesting for a Haskeller is the introductory discussion:

As a case in point, consider the problem of computing square roots. We can define the square-root function as √x = such that y >= 0 and y² = x. This describes a perfectly legitimate mathematical function…Indeed, it tells us almost nothing about how to actually find the square root of a given number. It will not help matters to rephrase this definition in pseudo-Lisp…This only begs the question.⁶

Immediately one recognizes the distinction between constructive and non-constructive definitions! It’s a long way from asserting that something exists (cf. the Axiom of Choice) and being able to create or demonstrate that something. This is a very profound distinction, and extremely important because any bit of logic which is constructive (‘Intuitionistic’) can be mechanically turned into a working program, of which all the same logical properties hold! This is the famous Curry-Howard isomorphism, and it’s very important for both Haskellers and FPers in general.

This was just a short aside to introduce a constructive method of taking square roots, and isn’t pursued any further. Oh well. Perhaps we can look forward to more asides like this? Although Lispers generally don’t seem too interested in FP languages’ connections to formal logics, so it’s doubtful.

Well, on to Newton’s method. That’s one recursive example you don’t see too often; and imagine, this textbook was written decades before people began whining about factorials and Fibonacci sequences!

(define (square x) (* x x)) ; defined in 1.1.4
(define (sqrt-iter guess x)
    (if (good-enough? guess x)
    guess
     (sqrt-iter (improve guess x) x)))

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

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

(define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))

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

square x = x*x

sqrtIter guess x = if goodEnough guess x
                            then guess
                            else sqrtIter (improve guess x) x

improve guess x = average guess (x / guess)

average x y = (x+y) / 2

goodEnough guess x = (abs $ (square guess) - x) < 0.001

sqrt x = sqrtIter 1.0 x

sqrtIter guess x = if goodEnough guess x then guess else sqrtIter (improve guess x) x

improve guess x = (guess + (x / guess)) / 2

goodEnough guess x = (abs $ (guess*guess) - x) < 0.001

sqrt x = sqrtIter 1.0 x

until (\x -> x < 0.001) (\x -> x / 2) 5
→ 6.103515625e-4

sqrt n lmt = until (\x -> abs (x^2 - n) <= lmt) (\x -> (x + (n / x)) / 2) 1

sqrt 25 0.0001
→ 5.000000000053722

root :: Float -> Float
root x = head (filter (satisfactory x) (iterate (improve x) 1))

satisfactory :: Float -> Float -> Bool
satisfactory x y = abs (y*y - x) < 0.01

improve :: Float -> Float -> Float
improve x y = (y + x/y)/2

(defun improve (guess x)
  (/ (+ (/ x (square guess))
        (* 2 guess))
     3))

cbrt n lmt = until (\x -> abs (x^3 - n) <= lmt) (\x -> (n/x^2 + 2*x) / 3) 1

1.1.8

This section pulls together our recursion from 1.1.7, and teaches us about black boxes, and how functions should be like them. The ‘Local names’ section came as something of a surprise to me; I’ve been programming in Haskell so long, which is like Scheme in being lexically scoped, that I’ve plumb forgotten about how name-shadowing is both counter-intuitive and also necessary for making a function reliable/referentially transparent!

This principle—that the meaning of a procedure should be independent of the parameter names used by its author—seems on the surface to be self-evident, but its consequences are profound. The simplest consequence is that the parameter names of a procedure must be local to the body of the procedure…A formal parameter of a procedure has a very special role in the procedure definition, in that it doesn’t matter what name the formal parameter has. Such a name is called a bound variable, and we say that the procedure definition binds its formal parameters. The meaning of a procedure definition is unchanged if a bound variable is consistently renamed throughout the definition. If a variable is not bound, we say that it is free. The set of expressions for which a binding defines a name is called the scope of that name. In a procedure definition, the bound variables declared as the formal parameters of the procedure have the body of the procedure as their scope.⁷