Feeds:
Posts

## SICP: Seeing a computer in software

As I’ve gone through SICP I’ve noticed a couple exercises that are very similar to programming problems we were given when I took Comparative Programming Languages in my sophomore year of college, when we were covering Lisp: 8 Queens (in Section 2.2.3 of SICP), and symbolic differentiation (in Section 2.3.2). I wonder if our professor got these problems out of this book, though they could’ve been classic computer science or AI problems. I’m going to focus on the symbolic differentiation exercises in this post.

The problem we were given in Comparative Programming Languages was to create a series of functions that would carry out all of the symbolic differentiation rules (for addition/subtraction, multiplication, division, and exponentiation) for expressions that had two, maybe a few more operands per operator (except for exponents), and simplify the resulting algebraic expressions. Our professor added, “I’ll give extra credit to anyone who implements the Chain Rule.” He gave us some helper functions to use, but we were expected to create the bulk of the code ourselves. In addition we could use no destructive operations (no set or setq). He wanted everything done in a pure functional style right off the bat. We had about a week or so to create a solution. We had only started covering Lisp the week before, and it was the first time in my life I had ever seen it. He never explained to us how a functional language worked. He was one of the hardest CS professors I had. What made it worse was he was terrible at teaching what he was trying to convey. He often came up with these really hard but interesting problems, though.

Creating the rules for addition/subtraction, and exponentiation were pretty easy once I had beaten my head against the wall for a while trying to understand how Lisp worked (I don’t think I ended up implementing the rules for multiplication and division). The hard part, which I didn’t even try, was simplifying the resulting expressions. I didn’t have the skill for it.

Having gone through that experience I was surprised by the treatment SICP gave to this exercise. On the first iteration it gave away almost everything I had tried to figure out myself for this assignment. I was wondering, “Gosh. This seemed like such a challenging book in the first chapter. It’s practically giving away the answers here!”

I’ll give the code for “deriv” as I think it’ll provide some clarity to what I’m talking about:

``````(define (deriv exp var)
(cond ((number? exp) 0)
((variable? exp)
(if (same-variable? exp var) 1 0))
((sum? exp)
(make-sum (deriv (addend exp) var)
(deriv (augend exp) var)))
((product? exp)
(make-sum
(make-product (multiplier exp)
(deriv (multiplicand exp) var))
(make-product (deriv (multiplier exp) var)
(multiplicand exp))))
(else (error "unknown type expression -- DERIV" exp))))
``````

The other functions that are needed to make this work are in the book. I modified the “else” clause, because PLTScheme doesn’t implement an “error” function. I use “display” instead.

SICP doesn’t ask the student to implement the differentiation rule for division, or the Chain Rule, just addition/subtraction, multiplication, and one of the exponentiation rules. The point wasn’t to make the exercise something that was hard to implement. It wasn’t about challenging the student on “Do you know how to do symbolic differentiation in code, recognize patterns in the algebra, and figure out how to simplify all expressions no matter what they turn out to be?” It wasn’t about making the student focus on mapping the rules of algebra into the computing domain (though there is some of that). It was about realizing the benefits of abstraction, and what a realization it is!

SICP asked me to do something which I had not been asked to do in all the years that I took CS, and had only occasionally been asked to do in my work. It asked me to take an existing structure and make it do something for which it did not appear to be intended. It felt like hacking, almost a little kludge-ish. I can see why I wasn’t asked to do this in college. What CS generally tried to do at the time was create good and proper programmers, instilling certain best practices. Part of that was writing clear, concise code, which was generally self-explanatory. A significant part of it as well was teaching structured programming, and demanding that students use it, in order to write clear code. That was the thinking.

What amazed me is SICP had me using the same “deriv” function–making no changes to it at all, except to add abstractions for new operations (such as exponentiation and subtraction)–to operate on different kinds of expressions, such as:

(+ (+ (expt x 2) (* 2 x)) 3)

(+ (+ x 3) (* 2 x) 3)

(((x + 3) + (2 * x)) + 3)

(x + 3 + 2 * x + 3) — (with operator precedence)

It could deal with all of them. All that was required was for me to change the implementation beneath the abstractions “deriv” used for each type of expression.

It brought to mind what Alan Kay said about objects–that an object is a computer. The reason I made this connection is the exercises forced me to break the semantic mapping I thought “deriv” was implementing, so that I could see “deriv” as just a function that computed a result–a specialized computer. Kay said that the abstraction is in the messages that are passed between objects in OOP, not in the objects. Here, I could see that the abstraction was in the function calls that were being made inside of “deriv”, not the code of “deriv”. The code is a pattern of use which is structured to follow certain rules. I could look at the function algebraically. In reality, the function names don’t mean anything that’s hard and fast. I thought to myself, “If I changed the implementation beneath the abstractions yet again–still not changing ‘deriv’–I might be able to do useful computing work on a different set of symbols, ones that aren’t even related to classical algebra.”

I recalled a conversation I remember reading online several years ago where a bunch of programmers were arguing over what were the best practices for creating abstractions in OOP. The popular opinion was that the objects should be named after real world objects, and that their behavior should closely model what happened in the real world. One programmer, though, had a different opinion. Whoever it was said that the goal shouldn’t be to structure objects and their relationships according to the real world equivalents, virtualizing the real world. Rather the goal should be to find computational processes that happen to model the real world equivalents well. So in other words, the goal, according to the commenter, should be to find a computer (I use the term “find” broadly, meaning to create one) that does what you need to do, and does it well, not try to take any old computing model and force it into a fashion that you think would model the real world equivalents well. The computer world is not some idealized version of the real world. It is its own world, but there are places where computing and real world processes intersect. The challenge is in finding them.

—Mark Miller, https://tekkie.wordpress.com