[SICP 5] Notes on SICP Chapter 1.1 “The Elements of Programming” - Sections 1.1.1, 1.1.2
Every computer program is a model, hatched in the mind, of a real or mental process. These processes, arising from human experience and thought, are huge in number, intricate in detail, and at any time only partially understood. [SICP]
1 Building Abstractions with Procedures
First chapter is about mastering functions, or as they are called in this book “procedures”, in describing a computational processes. They teach how to express a program in terms of function compositions and calls.
Authors pay extra attention to not do any variable assignments in their computations. They go full force functional, and compute everything without side-effects, without any deliberation on states until third chapter. Except when dealing with generic operations: in the second chapter they use a dictionary/table where users can store a function into given key. But even there, they only do an assignment once while loading libraries, and do not mutate the table ever again.
1.1 The Elements of Programming
Thinking in C vs. SICP
SICP teaches programming in a manner that is abstracted away from hardware. Starting this course without a former exposure to imperative programming paradigm could be an advantage.
The first programming language I’ve studied was C. And there, you are bounded by your understanding of lower-level stuff such as memory management at bytes level. The mental model is this linear memory, a tape if you will, where you place your objects whose memory blueprint needs to be carefully crafted too. You refer to them using pointers who live in their own separate memory addresses too. You open just enough space for an array of objects to live, and delete them after they are not needed anymore. In the meantime, pay special attention to not refer to the parts of the memory that is not intended to be touched. All of these cautions and preparations keeps the developers mind constantly busy while implementing actual processes that’ll handle the objects. This is definitely the right level for certain computational tasks, and also a lot to intake for beginner to start programmatic thinking.
In contrast, SICP starts with the idea of abstractions, hiding complexity behind interfaces with which users interact. Bits, bytes, memory layouts etc. are never mentioned. However, my past with low-level procedural languages haunted me and C-style anxieties of efficient the interpreter is going to handle a chunk of code occupied my mind until I got used to SICP’s approach. I think the idea behind the initial SICP exercises was that if your are given some primitive functions how to construct other functions.
Scheme as a formal system
SICP wants us to see Scheme as an algebra-like mathematical system, where evaluations are mathematical equivalency and simplification rules (where (x+y)^2 can be expanded to x^2+2xy+y^2 or the expanded expressions is factored into compact form). As opposed to a machinery that does computation by putting values into its registers and processes them according to instructions it reads from a memory tape.
The general name for such a system is called a “formal system”. If you never heard of this term before, MU puzzle from Gödel, Escher, Bach by Douglas Hofstadter can be a short example of what a formal system is and how they work.
A formal system has an alphabet and a set of characters. “Theorems” are expressed as strings, concatenations of characters from alphabet. There is a grammar, a set of rules, which are allowed manipulations on strings (theorems) to produce new strings (theorems). One starts with a set of strings, called axioms. A formal system is defined by an alphabet, a grammar and axioms. Given a formal system one can work on proving theorems.
There was even a research line in the foundations of mathematics called Formalism initiated by Hilbert to express whole mathematics as a formal system by making the definitions of theorems very precise and making theorem proving mechanical so that them (stuff in the meta of math) can become part of the math. This naive and ambitious research project failed spectacularly and led to Gödel’s Incompleteness theorem, but I digress.
Thinking about Scheme as a formal system is to approach the computations done by Scheme as “theorem proving in a formal systems”, i.e. application of grammar rules to manipulate one Scheme expression (theorem) to another one. Hence, here I try to pay special attention on Scheme’s grammar, the means of allowed manipulation on a syntactically correct expression. They discuss this approach explicitly in Chapter 1.1.5.
Also note that the formal system approach prevents adding arbitrary parentheses everywhere. Even though there are lots of them, you can’t add more unnecessarily. Not one more, not one less. :-)
Tools of abstraction
In short, first chapter of the book is about the elements of programming (especially procedures, data chapter comes later) and a how to construct them using the formal structure of Scheme, using its building blocks. Basic tools to combine simple ideas to form more complex ones in a programming language are as follows:
- primitive expressions (simplest entities that are given to us by the langugage/framework),
- means of combination (building compound elements from existing elements),
- means of abstraction (turning these combinations themselves in to building blocks). primitives, combination, abstraction…
1.1.1 Expressions
enter +, -, /, *
In Scheme’s RESP read-eval-print loop (I’ll emphasize new definitions using bold typeface) one can type an expression via the terminal (or input them from a file) and the interpreter will evaluate it and print the result.
- primitive expressions can be
- a constant (a literal such as a number or a string) or
- a variable name
- compound expressions can be
- a combination (a sequence of expressions enclosed in parentheses) or
- a special form (a parenthesized expression that starts with a reserved keyword)
Combinations denote a procedure application.
Authors make a distinction between syntactic entities (ex: a combination is an expression that has an operator and operands) vs. things manipulated in the language (ex: a procedure and the arguments to which it is applied). “The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands”. By the way, this notation of putting the operator before the operands is called prefix notation. (See Polish notation)
For binary operations such as arithmetic operations infix notation feels more natural and standard, but when the number of operands is more than 2 I think prefix is better. So, the + in Scheme is more like the summation symbol that sums items via $$\sum_{x \in X} x$$ rather than an operation that adds only two numbers x_1 + x_2.
Another advantage of prefix notation is that it allows nested combinations naturally where elements of combinations can be themselves combinations. (Even the operator can be a combination, or in better terms, a combination that evaluates into a procedure, but that won’t come in this early chapter).
Example nested expression in pretty-printed indentation format.
(+ (* 3
(+ (* 2 4)
(+ 3 5)))
(+ (- 10 7)
6))
1.1.2 Naming and the Environment
enter define
This section discusses the means of referring to computational objects using names. “The name identifies a variable whose value is the object.” Naming is done via define. define is the simplest mean of an abstraction. It creates a binding between the name given in the second argument and the value in the third argument. define is also a special form, an exception among compound expressions, a topic that’s discussed later.
After they are defined, names become primitive expressions which can be evaluated alone or be part of a compound expression.
A later definition can refer to a former definition. This allows to construct a program incrementally in increasing complexity. “name-object associations can be created incrementally in successive interactions” The example they give is as follows:
(define pi 3.14159)
(define radius 10)
(define circumference (* 2 pi radius)) ; is aware of pi and radius
circumference stores ; stores the result of the computation
62.8318
Each definition can be tested separately.
Since everything is evaluated by the interpreter, define expressions are also evaluated and their value is printed in return. That return value is implementation dependent and has no significant value. MIT-Scheme returns the name, Racket doesn’t return anything.
Definitions are both similar to and different from variable assignments in imperative languages. Similar in the sense that now we can refer to entities/values by their names. However, the difference is that these defines are meant to be used only once per name (in the same scope).
Re-defining a symbol using multiple define statements for the same symbol threw an error.
(define x 1)
(define x 2)
(display x)
> 2 in MIT Scheme
> "identifier already defined in: x" in Racket
(define (f) ; function definition we'll study in the next post
(define x 1)
(define x 2)
(display x))
> "duplicate internal definitions for (#[uninterned-symbol 12 x]) in f" in MIT Scheme
> "letrec-values: duplicate binding name in: x" in Racket
Apparently, as an exception MIT Scheme allows redefinitions only in global scope. For all other cases define on the same symbol is forbidden.
However, for now, I want to confuse the readers with following seeming re-assignments in a loop which outputs 1 2 3. (Actually it is not doing re-assignments. But first we have to learn about recursive procedures and how to express iteration over a list of items via recursion. All to be seen later in chapter 1.)
(map
(lambda (x)
(define num x) ; are we re-defining num here over the loop?!
(display num))
(list 1 2 3))
Because things can be retrieved later in the execution, the name-object associations has to be stored somewhere in the memory while associations are being “created incrementally in successive interactions” with the interpreter. The memory location for this storage is called an environment. In this specific instance it’s the global environment.
One unusual feature of Scheme syntax is its allowance of any characters in names. The only special characters that can’t be used are white spaces and parenthesis. So, pi*2*, 2*pi ,three-word-name, why?, do-it! are totally valid names in Scheme!
tags: