sicp 1.13 - higher order functions

tttaaannnggg profile image tang ・3 min read

sicp (3 Part Series)

1) What I learned today (SICP 1.1) 2) SICP 1.2 - Ackermann's Function and Contemplating Infinity 3) sicp 1.13 - higher order functions

Whew, the math really starts kicking in on this one. I'm working off of this lecture series alongside the book itself, and honestly, I haven't been able to finish the entire problemset, but I'm trying to keep myself on track with 2 lessons per week, so here we are.

I had a bit of trouble following Hal, since the way that these concepts are applied is geared towards solving math problems- in this case, how to calculate a square root.

I'll skip past a lot of it, but there are a few core concepts that I got out of this lesson that are a bit unrelated to the concept of higher order functions, but are implemented through higher order functions.

what is a derivative?

I'll talk about derivatives first, since that's the thing i've got the most context for.

As I understand them (from my memories of highschool calculus), derivatives are functions that describe the rate of change of another function. i.e. if you have f(x) = 3x + 5, and chart it out, you'll notice a pattern:

f(0) = 5
f(1) = 8
f(2) = 11
f(3) = 14

every time x increases by 1, f(x) increases by 3. so what's the derivative of f(x)? 3.

pretty simple so far, right? we generally use the notation f'(x) (notice the ' to denote a derivative. f'(x), pronounced "f prime of x", is a function that describes the rate of change in f(x).

I'm not going to teach you how to do derivatives the mathy way, but I'll at least say that they get more complicated as the functions you're differentiating get more complicated. for instance, we can look at the following:

f(x)  = x^2 + 2x + 5
f'(x) = 2x + 2

f(x) changes at a rate of f'(x), which makes sense, doesn't it? if we chart out f(x), it grows faster and faster as x increases, rather than growing steadily like our previous example does.

Anyways, if we want to bring it back to dealing with higher order functions, I'll put it this way: taking the derivative of a function f(x) produces a function that describes the rate of change of f(x). In other words, we can think of a derivative as a higher order function.

How do we find a derivative?

How would we figure out what that function is?

Getting the real deal is a bit... difficult / I have no idea at my level, but we can approximate it.

There's a mathematical definition for a derivative:

f'(x) = (f(x + dx) - f(x))/(dx)
as dx -> 0

this will need a little bit of explaining as well. If we think about our previous example, where we took the derivative of f(x) = 3x + 5, what were we doing?

Well, we put f(0) in, then f(1), and calculated the difference between them. f(1) - f(0). That gives us the total change between f(0) and f(1), but how do we get the rate at which it's changing? The change in total amount divided by the extent to which we changed our input will give us the answer.


f'(x) = (f(x + dx) - f(x))/(dx)
as dx -> 0

dx, thus, represents the amount by which we change our inputs. but why as dx -> 0?

We want to produce a function that is able to tell us what the rate of change is at any point in f(x), so we need a function that is continuous. The only way we get that is by using a dx that is so infinitesimally small that it's basically 0.

For the purposes of this function, though, we're only estimating a derivative, so we'll give it an arbitrary small value. something like dx = 0.0000001 will be good enough for us.

Implementation in Scheme

With all that being said, all we have to do is translate that into scheme, as follows:

(define derivative 
  (lambda (f)
    (define dx 0.000001)
    (lambda (x)
      (/ (- (f (+ x dx)) (f x)) dx))))

in this function definition, derivative is defined as a lambda function that takes in a function f, defines a dx to be 0.000001 and returns a lambda function that takes in some x and uses our previous formula to compute the rate of change in f at x. This is not a perfect answer, but it's close enough for some uses.

sicp (3 Part Series)

1) What I learned today (SICP 1.1) 2) SICP 1.2 - Ackermann's Function and Contemplating Infinity 3) sicp 1.13 - higher order functions

Posted on by:

tttaaannnggg profile



"Poets do not go mad; but chess-players do. Mathematicians go mad, and cashiers; but creative artists very seldom." -GK Chesterton


markdown guide