"Structure and Interpretation of Computer Programs" (sicp) is a book that analyzes general (language and hardware-independent) concepts used in computer program development in great detail. Despite being 30 years old this book still enjoys great popularity among computer scientists which proves that its content is timeless. This is in great contrast to other topics in software development which are outdated quickly.
The entire book can be viewed online.
Below you can find a dictionary with terms from the book. The descriptions are phrased in my own words
| Concept Description | Book Section |
|---|---|
| A procedure is a specific sequence of statements. The sequence can contain placeholders (parameters). When a procedure is "called", the sequence of statements is executed. If the sequence contained placeholders, the call to the procedure needs to include the values to be substituted for the placeholders. (These substitution happen only in the places before assignments are made to the placeholders in the code, see substitution vs environment model) | 1 |
| A procedure describes a computational process. A process is a sequence of elementary operations that are executed in strict order. While a procedure is also a sequence of operations, it can be represented by different processes. It is the job of the interpreter to use an efficient process for a given procedure. A tail-recursive procedure for example can be converted into an iterative process. | 1 |
| A combination is a list of expressions separated by blanks surrounded by parenthesis. This typically invokes a procedure with the name of the first expression in the list (operator). The following symbols are used as arguments to the procedure (operands). | 1.1.1 |
| Arguments are the values that are passed to a procedure upon procedure invocation. | 1.1.1 |
| define assigns a name to a symbol, saving this association into the local environment. Subsequent uses of the name are replaced by the associated symbol in the current scope (and its nested (sub-)scopes). Procedures can also be created with define (without the use of lambda). As opposed to lambda a name is associated with the procedure. Thus, the following two are equivalent (define add (lambda (x y) (+ x y)) and (define (add x y) (+ x y)) | 1.1.2 |
| An environment is a set of symbol definitions. Where the environment can be accessed (see "scope") the symbols are replaced by their definitions in the environment. | 1.1.2 |
| Recursion is a property of procedures and processes that states that they contain calls to themselves. Many problems can be expressed very elegantly as recursion but recursion can be space and time demanding because local variables need to be conserved and parameters passed for every call. | 1.1.3 |
| Special forms are special lisp functions that cannot be implemented with an ordinary lisp function definition i.e. define or lambda that would be evaluated by he interpreter. Instead special forms are build into the interpreter to allow for a higher level of control. 'define' for example needs as the first argument the to-be-defined function name with its accepted arguments. In a normal evaluation te interpreter would try to evaluate that expression i.e. apply a function with that name to the expanded variables that follow. Instead the interpreter uses special rules to evaluate the 'define' creating a new symbol to be added to the environment. | 1.1.3 |
| In a procedure definition the formal parameters specify what arguments the procedure expects. The arguments are then used to fill the placeholders inside the procedure. | 1.1.4 |
| The substitution model is a recipe for evaluating procedures. Upon procedure invocation each appearance of a parameter name inside the procedure's code is substituted with the value that was passed to the corresponding parameter on this procedure invocation. Then the statements can be evaluated. The substitution model breaks once assignment is allowed in a programming language (see environment model). | 1.1.5 |
| In applicative-order evaluation inner-most parenthesis are evaluated/expanded first. In normal-order evaluation the outer-most parenthesis are evaluated/expanded first. Applicative-order evaluation is usually more efficient as normal-order tends to expand the entire code before reducible calculation with primitives can be executed. | 1.1.5 |
| With if and cond different paths of execution can be specified. Predicates can be used to decide which path to walk. | 1.1.6 |
| A predicate is a mathematical function that evaluates to a boolean. | 1.1.6 |
| The goal of procedureal abstraction is to free the user from the burden to know the details about a procedure's implementation. The procedure name, the parameters and documentation is supposed to be sufficient for the user to be able to use the procedure. | 1.1.8 |
| A scope is a location in the code in which certain environments can be accessed. Scopes can be nested, see "block structure". Symbols in inner scopes "shadow" symbols with the same name in a more outer scope, i.e. the inner scope's definition is used as opposed to the outer scope's definition. | 1.1.8 |
| Programming languages that have block structure allow scopes to be nested and allows all kinds of symbol definitions to appear at every level of nesting. | 1.1.8 |
| Lexical scoping is the programming language features that allows code in a certain scope to access all the symbol definition from the surrounding scopes while at the same time giving all scopes defined in that scope access to symbols previously defined in that scope. | 1.1.8 |
| A linear recursive process is one for which the space/time (i.e. memory/operations) requirements grow linearly with respect to the input parameter(s) | 1.2.1 |
| Iterative processes need only a fixed amount of state variables to execute irrespective of the input parameter. This allows representation by a loop which is smaller and faster than a recursive process. | 1.2.1 |
| In a tail-recursive procedure, the call to itself is executed right before the procedure is finished. These procedures can be translated into iterative processes trivially. Scheme does so. | 1.2.1 |
| Probabilistic algorithms don't give a correct output with absolute certainty. This can still be useful when their accurate counterparts have a much higher demand for computation/memory. They might indicate cases on which a demanding accurate implementation needs to be applied to get absolute results and sort out other cases which are not of interest. | 1.2.6 |
| Higher-order procedures take procedures as parameters or return procedures. | 1.3 |
| lambda creates a procedure. In a call to lambda, the parameters (placeholders) to be used in the sequence, need to be specified. Also, the sequence of statements needs to be specified. lambda does not give a name to the procedure that is created. Thus, usage of lambda only makes sense when a procedure needs to be passed as a parameter to another procedure. A name could be assigned to the procedure via "let" or "define" but that would be awkward because "define" also gives a more direct syntax for creating a procedure (without lambda). | 1.3.2 |
| let allows the programmer to define symbols for a specified section of code. Thus let allows the creation of a scope. | 1.3.2 |
| In Lisp/Scheme procedures have first-class status, i.e. they can be assigned to variables, passed as parameters, defined during evaluation, | 1.3.4 |
| Concept Description | Book Section |
|---|---|
| New data types can be created via combination of the primitive data type provided by lisp. One essential language features that allows these so-called compound data to be created is the pair which also allows the creation of list. | 2 |
| Data abstraction aims to make the details of the representation of data independent of the interface used to interact with the data. This way a user of the data doesn't need to know how the data is represented but only the procedures used to create and access the data, see selectors and constructors. | 2 |
| Data interaction can be modeled in a way that is independent from its representation. This is accomplished by the use of procedures that construct and procedures that retrieve the data, called constructors and selectors respectively. For a simple example look at a pair whose constructor is cons and the selectors are car and cdr. | 2.1 |
| In wishful thinking one assumes a specific interface for some module that might not be existant/implemented, yet. With this interface dependent modules can already be implemented despite the fact that the lower level details aren't implemented, yet. | 2.1.1 |
| A pair is a primitive data object whose purpose is to store two arbitrary objects. This allows the construction of arbitrarily complex composed objects. Any set of procedures (cons,car,cdr) for which the predicates (car (cons a b)) == a and (cdr (cons a b)) == b evaluate to true (#t) can implement the notion of a pair. |
2.1.1 |
| Abstraction barriers exist in highly modularized code. Here groups of procedures can be put into layers where each layer's procedures call only procedures of its own level and the layer below. This allows procedures in the higher levels to be ignorant of the details of the lower levels far below. Every layer abstracts the details of the layers below for the higher layer procedures and thus also represents a barrier for the procedures of higher layers which only calls procedures of this layer and not below. | 2.1.2 |
| Church numerals are a representation for whole numbers. The whole number is given by the amount of consecutive operation applications. This amount is encoded by a higher-order procedure which takes as an argument any operation that has closure. | 2.1.3 |
| Closure is a property that operations can possess. It indicates that the input of an operation is of the same type as the output of the operation. Thus the operation can be applied to the input several times, i.e. with the output of the operation application being the input of the next operation application. | 2.2 |
| In a hierarchical structure items have a set of "child"-items associated with them and can themselves be a child part of one "parent" item. list of 'lower' have a set of list all parts of an element are If a collection of items is arranged in a hierarchical structure, every item can be reached by walking from a single root element are arranged | 2.2 |
| A sequence is a set of items arranged in a certain order. | 2.2.1 |
| Sequences can be represented by a Scheme list. Here every item is stored in the first element of a pair while the second element of the pair is used to connect to the next item in the sequence. | 2.2.1 |
| The item nil is used to mark the end of a list. In the pair that contains the last item the second element points to nil. Thus, nil itself also represents an empty list. | 2.2.1 |
| A procedure can accept an arbitrary amount of arguments. Dotted-tail notation needs to be used to indicate such a procedure (e.g. define (proc a b . c) ....). The arguments that are not captured by the normal parameter list are handed to the procedure inside a list that is accessible inside the procedure via the name given after the dot (the variable name would be 'c' in the previously shown example). | 2.2.1 |
| The operations map flatmap usually apply a given procedure to every element in a list and return a list of the processed items. If the processed items are themselves lists flatmap also "extracts" these items to return only items and no lists. | 2.2.1 |
| Sequences can also be represented in a tree instead of a list. Just like a list a tree uses pairs to store items. The difference is that in a tree both elements of the pair may be either items or other pairs (or nil). | 2.2.2 |
| The operation enumerate converts from the tree representation to the list representation. | 2.2.3 |
There is a conventional interface for sequences that most programming laguages adhere to these days. It consists of a set of basic operations that are frequently used when sequences are being processed. These operations conventionally have names, like
| 2.2.3 |
| The operation filter applies a supplied predicate to every item in a list and returns only the items for which the predicate evaluated to 'true' (#t). | 2.2.3 |
| Operations with names like reduce accumulate aggregate fold fold-left fold-right take a list as argument and a procedure that takes two items of the list and returns a single item of the same type. The operations apply the given procedure repeatedly to all the items of the list together with the result of the previous procedure application until only a single element is left which is then returned. | 2.2.3 |
| Stratified design denominates a layered structure in the sets of procedures/modules in a program. The procedures in each layer only call procedures of the layers below it. | 2.2.4 |
| Identifiers in Scheme can be stored in a variable. This is called symbolic data. When mentioning an identifier in code it is usually replaced with the value it stands for. To allow referencing the identifier name itself it has to be preceded by a single quote: 'name. If a list is preceded by a quote all character sequences that appear inside the list are interpreted as symbolic data. | 2.3 |
| Generic operations can work with different representations of the same data transparently. The type of representation is stored as part of the data. | 2.4.1 |
| Type tags can be attached to data to allow the use of generic procedure names. A system designed in this way selects the proper type-specific code using the tag name. This is used in data-directed programming or when using generic procedures. | 2.4.2 |
| In data-directed programming selection of the right type-specific operations is not done inside a generic procedure. Instead separate type-specific procedures are registered in a table under a generic procedure name. To invoke a procedure on some data an 'apply-generic' procedure that accepts a generic procedure name retrieves and executes the right procedure for the given data type. Procedures for one data type can be supplied in installable packages. With this architecture existing systems can be enhanced with further type support additively. | 2.4.3 |
| In dispatch on type the data object itself returns the appropriate procedure for its own type. | 2.4.3 |
| In message passing one can request a procedure from a data object. The data object provides a procedure which returns the requested procedure. | 2.4.3 |
| When there are multiple representations for equivalent data but our procedures only work for a particular set of represenetations, coercion converts the data between types trying to find a compatible one. It usually uses a so-called coersion table to look for applicable conversions. | 2.5.2 |
| Sometimes certain data representations are more generic than others. That means data in one type can be represented in the other type but not the other way round. If that's the case the different represenetations can be arranged in a hierarchy of types. The element above the current one is referred to as supertype, the one below as subtype. | 2.5.2 |
| A tower is a linear hierarchy of types. If the data representations form a tower, coercion becomes particularly simple. Data can simply be converted up (or even down) the type hierarchy until the needed type is reached. | 2.5.2 |
| If a data type is composed of other data types, an operation of the former may trigger the same generic operation to be invoked on the subtypes. This is called data-directed recursion. | 2.5.3 |
| Concept Description | Book Section |
|---|---|
| Assignment allows us to change the data that is referenced with an identifier. Without it identifiers can only be initialized with data and not be changed until the scope that the identifier is defined in is left at which time the identifier is not valid/accessible anymore. Allowing assignment invalidates the substitution model for computation and instead requires the more complicated environment model to correctly describe computation. | 3.1 |
| The environment model is a recipe for evaluating procedures. Once assignment is allowed in a programming language it replaces the substitution model. Each parameter has its own storage associated with it for every procedure invocation. Upon invocation this storage is set to the values passed into the procedure arguments. During execution of the procedure body the values in the storage can be read and set (assignment). | 3.2 |
| The same way we defined selectors to be retrieve data from an object in data abstraction. A mutator allows us to change the data stored in the object. In the case of a pair we had the two selectors car and cdr. Now, we add the two mutators set-car! and set-cdr! to also allow manipulation of the two items in the pair. | 3.3 |
| A queue is a storage for sequences that is optimized to allow efficient retrieval and removal of the items that are at the front of the sequence and to allow for efficient addition of items to the end of the sequence. This kind of storage is sometimes refered to as FIFO (first in first out). | 3.3.2 |
| In sicp a table is refered to a datastructure that hold key-value pairs i.e. a list of pairs of associated items. | 3.3.3 |
| Memoization or tabulation is a programming technique in which results calculated by deterministic (stateless) procedure are stored together with the parameters passed to the procedure. In a consecutive call to he procedure a lookup is performed to see if the procedure was called before with the provided arguments. If so, the stored result is returned rather than performing the calculation again which saves time. | 3.3.3 |
| In an event-driven simulation an object "wakes-up" and reacts when a certain thing happens. This is done by registering the object to be woken up with the object that causes the event. When the event occurs the object causing the event notifies all registered objects about it. | 3.3.4 |
| Propagation of constraints can be used to automatically update objects in response to a change in another object. The change triggers an adjustment in the data of the dependent objects which in turn trigger an update in their dependees. This way a change is propagated through a chain of objects to ensure that constraints between the objects are fulfilled. | 3.3.5 |
| A constraint network uses propagation of constraints to relate data in different objects to each other. Data that is provided for some objects causes connected objects to update so that contraints (dependencies) among objects are always fulfilled. The dependent objects can be read out which contain the solution to a problem. If data for too many objects is provided the constrains can be violated in which case an error is emitted. | 3.3.5 |
| When using sequential processing one can always assume that nothing gets executed between two adjacent statements. This is in contrast to concurrent processing where contraol can be passed to another process after each statement. | 3.4 |
| Concurrency specifies that processes can execute in an interleaved or parallel fashion, i.e. one process starts executing code before the other one finishes on the same code. When processes share and modify the same resources special care needs to be taken in order to obtain the same final result as if the processes were executed sequentially. | 3.4 |
| Restrictions on concurrency are necessary to make code that is executed concurrently equivalent to code that is executed sequentially. In particular one would expect the same end result (either strictly quantitative or just qualitative). Weather we also require intermediate results to coinceed is up taste and optimization. In a diffusion simulation for example a speed-up can be obtained by allowing deviations in intermediate results as compared to sequential code. Despite this we can regard the code as equivalent because the simulation still converges to the same end result. | 3.4.1 |
| A serializer ensures that a procedure is only executed by a single process at a time. It can wrap around the procedure to be serialized and uses a mutex to make other processes wait. | 3.4.1 |
| Mutexes are used in concurrent systems to avoid execution of specific sections of code by two concurrently running processes. When one process aquires a mutex all other processes have to wait once they try to execute the same section of code. When the first process releases the mutex after the critical section of the code has been executed one of the waiting processes will be able to aquire it and start execution. | 3.4.1 |
| An operation is said to be atomic if it is executed in one go. Control can not resume in another process while the operation executes. Test-and-set is a typical example of such an operation. | 3.4.1 |
| A semaphore is similar to a mutex but lets a specified amount of processes acquire it. | 3.4.1 |
| A deadlock occurs when processes wait for each other to release mutexes. | 3.4.1 |
