/prog/ - Writing SICP, since you never read it.

Name: Anonymous 2021-03-16 8:46

These 2011 nostalgia autists didn't expect that:

Structure and Interpretation
of Computer Programs

second edition 





Harold Abelson and Gerald Jay Sussman
with Julie Sussman 

foreword by Alan J. Perlis 







The MIT Press
Cambridge, Massachusetts     London, England

McGraw-Hill Book Company
New York     St. Louis     San Francisco     Montreal     Toronto 


 This book is one of a series of texts written by faculty of the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology. It was edited and produced by The MIT Press under a joint production-distribution arrangement with the McGraw-Hill Book Company.

Ordering Information:

North America
Text orders should be addressed to the McGraw-Hill Book Company.
All other orders should be addressed to The MIT Press.

Outside North America
All orders should be addressed to The MIT Press or its local distributor.

© 1996 by The Massachusetts Institute of Technology

Second edition

Creative Commons License
Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Jay Sussman with Julie Sussman is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License by the MIT Press.

This book was set by the authors using the LATEX typesetting system and was printed and bound in the United States of America.

Library of Congress Cataloging-in-Publication Data

Abelson, Harold
    Structure and interpretation of computer programs / Harold Abelson
and Gerald Jay Sussman, with Julie Sussman. -- 2nd ed.
    p. cm. -- (Electrical engineering and computer science
series)
    Includes bibliographical references and index.
    ISBN 0-262-01153-0 (MIT Press hardcover)
    ISBN 0-262-51087-1 (MIT Press paperback)
    ISBN 0-07-000484-6 (McGraw-Hill hardcover)
    1. Electronic digital computers -- Programming. 2. LISP (Computer
program language) I. Sussman, Gerald Jay. II. Sussman, Julie.
III. Title. IV. Series: MIT electrical engineering and computer
science series.
QA76.6.A255         1996
005.13'3 -- dc20              96-17756

Fourth printing, 1999 

 This book is dedicated, in respect and admiration, to the spirit that lives in the computer.

``I think that it's extraordinarily important that we in computer science keep fun in computing. When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every now and then, and after a while we began to take their complaints seriously. We began to feel as if we really were responsible for the successful, error-free perfect use of these machines. I don't think we are. I think we're responsible for stretching them, setting them off in new directions, and keeping fun in the house. I hope the field of computer science never loses its sense of fun. Above all, I hope we don't become missionaries. Don't feel as if you're Bible salesmen. The world has too many of those already. What you know about computing other people will learn. Don't feel as if the key to successful computing is only in your hands. What's in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.''

Alan J. Perlis (April 1, 1922-February 7, 1990)


Contents

    Foreword

    Preface to the Second Edition

    Preface to the First Edition

    Acknowledgments

    1  Building Abstractions with Procedures
        1.1  The Elements of Programming
            1.1.1  Expressions
            1.1.2  Naming and the Environment
            1.1.3  Evaluating Combinations
            1.1.4  Compound Procedures
            1.1.5  The Substitution Model for Procedure Application
            1.1.6  Conditional Expressions and Predicates
            1.1.7  Example: Square Roots by Newton's Method
            1.1.8  Procedures as Black-Box Abstractions
        1.2  Procedures and the Processes They Generate
            1.2.1  Linear Recursion and Iteration
            1.2.2  Tree Recursion
            1.2.3  Orders of Growth
            1.2.4  Exponentiation
            1.2.5  Greatest Common Divisors
            1.2.6  Example: Testing for Primality
        1.3  Formulating Abstractions with Higher-Order Procedures
            1.3.1  Procedures as Arguments
            1.3.2  Constructing Procedures Using Lambda
            1.3.3  Procedures as General Methods
            1.3.4  Procedures as Returned Values

    2  Building Abstractions with Data
        2.1  Introduction to Data Abstraction
            2.1.1  Example: Arithmetic Operations for Rational Numbers
            2.1.2  Abstraction Barriers
            2.1.3  What Is Meant by Data?
            2.1.4  Extended Exercise: Interval Arithmetic
        2.2  Hierarchical Data and the Closure Property
            2.2.1  Representing Sequences
            2.2.2  Hierarchical Structures
            2.2.3  Sequences as Conventional Interfaces
            2.2.4  Example: A Picture Language
        2.3  Symbolic Data
            2.3.1  Quotation
            2.3.2  Example: Symbolic Differentiation
            2.3.3  Example: Representing Sets
            2.3.4  Example: Huffman Encoding Trees
        2.4  Multiple Representations for Abstract Data
            2.4.1  Representations for Complex Numbers
            2.4.2  Tagged data
            2.4.3  Data-Directed Programming and Additivity
        2.5  Systems with Generic Operations
            2.5.1  Generic Arithmetic Operations
            2.5.2  Combining Data of Different Types
            2.5.3  Example: Symbolic Algebra

    3  Modularity, Objects, and State
        3.1  Assignment and Local State
            3.1.1  Local State Variables
            3.1.2  The Benefits of Introducing Assignment
            3.1.3  The Costs of Introducing Assignment
        3.2  The Environment Model of Evaluation
            3.2.1  The Rules for Evaluation
            3.2.2  Applying Simple Procedures
            3.2.3  Frames as the Repository of Local State
            3.2.4  Internal Definitions
        3.3  Modeling with Mutable Data
            3.3.1  Mutable List Structure
            3.3.2  Representing Queues
            3.3.3  Representing Tables
            3.3.4  A Simulator for Digital Circuits
            3.3.5  Propagation of Constraints
        3.4  Concurrency: Time Is of the Essence
            3.4.1  The Nature of Time in Concurrent Systems
            3.4.2  Mechanisms for Controlling Concurrency
        3.5  Streams
            3.5.1  Streams Are Delayed Lists
            3.5.2  Infinite Streams
            3.5.3  Exploiting the Stream Paradigm
            3.5.4  Streams and Delayed Evaluation
            3.5.5  Modularity of Functional Programs and Modularity of Objects

    4  Metalinguistic Abstraction
        4.1  The Metacircular Evaluator
            4.1.1  The Core of the Evaluator
            4.1.2  Representing Expressions
            4.1.3  Evaluator Data Structures
            4.1.4  Running the Evaluator as a Program
            4.1.5  Data as Programs
            4.1.6  Internal Definitions
            4.1.7  Separating Syntactic Analysis from Execution
        4.2  Variations on a Scheme -- Lazy Evaluation
            4.2.1  Normal Order and Applicative Order
            4.2.2  An Interpreter with Lazy Evaluation
            4.2.3  Streams as Lazy Lists
        4.3  Variations on a Scheme -- Nondeterministic Computing
            4.3.1  Amb and Search
            4.3.2  Examples of Nondeterministic Programs
            4.3.3  Implementing the Amb Evaluator
        4.4  Logic Programming
            4.4.1  Deductive Information Retrieval
            4.4.2  How the Query System Works
            4.4.3  Is Logic Programming Mathematical Logic?
            4.4.4  Implementing the Query System

    5  Computing with Register Machines
        5.1  Designing Register Machines
            5.1.1  A Language for Describing Register Machines
            5.1.2  Abstraction in Machine Design
            5.1.3  Subroutines
            5.1.4  Using a Stack to Implement Recursion
            5.1.5  Instruction Summary
        5.2  A Register-Machine Simulator
            5.2.1  The Machine Model
            5.2.2  The Assembler
            5.2.3  Generating Execution Procedures for Instructions
            5.2.4  Monitoring Machine Performance
        5.3  Storage Allocation and Garbage Collection
            5.3.1  Memory as Vectors
            5.3.2  Maintaining the Illusion of Infinite Memory
        5.4  The Explicit-Control Evaluator
            5.4.1  The Core of the Explicit-Control Evaluator
            5.4.2  Sequence Evaluation and Tail Recursion
            5.4.3  Conditionals, Assignments, and Definitions
            5.4.4  Running the Evaluator
        5.5  Compilation
            5.5.1  Structure of the Compiler
            5.5.2  Compiling Expressions
            5.5.3  Compiling Combinations
            5.5.4  Combining Instruction Sequences
            5.5.5  An Example of Compiled Code
            5.5.6  Lexical Addressing
            5.5.7  Interfacing Compiled Code to the Evaluator

    References

    List of Exercises

    Index

Name: Anonymous 2021-03-16 9:49

Exercise 4.1.  Notice that we cannot tell whether the metacircular evaluator evaluates operands from left to right or from right to left. Its evaluation order is inherited from the underlying Lisp: If the arguments to cons in list-of-values are evaluated from left to right, then list-of-values will evaluate operands from left to right; and if the arguments to cons are evaluated from right to left, then list-of-values will evaluate operands from right to left.

Write a version of list-of-values that evaluates operands from left to right regardless of the order of evaluation in the underlying Lisp. Also write a version of list-of-values that evaluates operands from right to left.

4.1.2  Representing Expressions

The evaluator is reminiscent of the symbolic differentiation program discussed in section 2.3.2. Both programs operate on symbolic expressions. In both programs, the result of operating on a compound expression is determined by operating recursively on the pieces of the expression and combining the results in a way that depends on the type of the expression. In both programs we used data abstraction to decouple the general rules of operation from the details of how expressions are represented. In the differentiation program this meant that the same differentiation procedure could deal with algebraic expressions in prefix form, in infix form, or in some other form. For the evaluator, this means that the syntax of the language being evaluated is determined solely by the procedures that classify and extract pieces of expressions.

Here is the specification of the syntax of our language:

¤ The only self-evaluating items are numbers and strings:

(define (self-evaluating? exp)
  (cond ((number? exp) true)
        ((string? exp) true)
        (else false)))

¤ Variables are represented by symbols:

(define (variable? exp) (symbol? exp))

¤ Quotations have the form (quote <text-of-quotation>):9

(define (quoted? exp)
  (tagged-list? exp 'quote))

(define (text-of-quotation exp) (cadr exp))

Quoted? is defined in terms of the procedure tagged-list?, which identifies lists beginning with a designated symbol:

(define (tagged-list? exp tag)
  (if (pair? exp)
      (eq? (car exp) tag)
      false))

¤ Assignments have the form (set! <var> <value>):

(define (assignment? exp)
  (tagged-list? exp 'set!))
(define (assignment-variable exp) (cadr exp))
(define (assignment-value exp) (caddr exp))

¤ Definitions have the form

(define <var> <value>)

or the form

(define (<var> <parameter1> ... <parametern>)
  <body>)

The latter form (standard procedure definition) is syntactic sugar for

(define <var>
  (lambda (<parameter1> ... <parametern>)
    <body>))

The corresponding syntax procedures are the following:

(define (definition? exp)
  (tagged-list? exp 'define))
(define (definition-variable exp)
  (if (symbol? (cadr exp))
      (cadr exp)
      (caadr exp)))
(define (definition-value exp)
  (if (symbol? (cadr exp))
      (caddr exp)
      (make-lambda (cdadr exp)   ; formal parameters
                   (cddr exp)))) ; body

¤ Lambda expressions are lists that begin with the symbol lambda:

(define (lambda? exp) (tagged-list? exp 'lambda))
(define (lambda-parameters exp) (cadr exp))
(define (lambda-body exp) (cddr exp))

We also provide a constructor for lambda expressions, which is used by definition-value, above:

(define (make-lambda parameters body)
  (cons 'lambda (cons parameters body)))

¤ Conditionals begin with if and have a predicate, a consequent, and an (optional) alternative. If the expression has no alternative part, we provide false as the alternative.10

(define (if? exp) (tagged-list? exp 'if))
(define (if-predicate exp) (cadr exp))
(define (if-consequent exp) (caddr exp))
(define (if-alternative exp)
  (if (not (null? (cdddr exp)))
      (cadddr exp)
      'false))

We also provide a constructor for if expressions, to be used by cond->if to transform cond expressions into if expressions:

(define (make-if predicate consequent alternative)
  (list 'if predicate consequent alternative))

¤ Begin packages a sequence of expressions into a single expression. We include syntax operations on begin expressions to extract the actual sequence from the begin expression, as well as selectors that return the first expression and the rest of the expressions in the sequence.11

(define (begin? exp) (tagged-list? exp 'begin))
(define (begin-actions exp) (cdr exp))
(define (last-exp? seq) (null? (cdr seq)))
(define (first-exp seq) (car seq))
(define (rest-exps seq) (cdr seq))

We also include a constructor sequence->exp (for use by cond->if) that transforms a sequence into a single expression, using begin if necessary:

(define (sequence->exp seq)
  (cond ((null? seq) seq)
        ((last-exp? seq) (first-exp seq))
        (else (make-begin seq))))
(define (make-begin seq) (cons 'begin seq))

¤ A procedure application is any compound expression that is not one of the above expression types. The car of the expression is the operator, and the cdr is the list of operands:

(define (application? exp) (pair? exp))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))
(define (no-operands? ops) (null? ops))
(define (first-operand ops) (car ops))
(define (rest-operands ops) (cdr ops))

Derived expressions

Some special forms in our language can be defined in terms of expressions involving other special forms, rather than being implemented directly. One example is cond, which can be implemented as a nest of if expressions. For example, we can reduce the problem of evaluating the expression

(cond ((> x 0) x)
      ((= x 0) (display 'zero) 0)
      (else (- x)))

to the problem of evaluating the following expression involving if and begin expressions:

(if (> x 0)
    x
    (if (= x 0)
        (begin (display 'zero)
               0)
        (- x)))

Implementing the evaluation of cond in this way simplifies the evaluator because it reduces the number of special forms for which the evaluation process must be explicitly specified.

We include syntax procedures that extract the parts of a cond expression, and a procedure cond->if that transforms cond expressions into if expressions. A case analysis begins with cond and has a list of predicate-action clauses. A clause is an else clause if its predicate is the symbol else.12

(define (cond? exp) (tagged-list? exp 'cond))
(define (cond-clauses exp) (cdr exp))
(define (cond-else-clause? clause)
  (eq? (cond-predicate clause) 'else))
(define (cond-predicate clause) (car clause))
(define (cond-actions clause) (cdr clause))
(define (cond->if exp)
  (expand-clauses (cond-clauses exp)))

(define (expand-clauses clauses)
  (if (null? clauses)
      'false                          ; no else clause
      (let ((first (car clauses))
            (rest (cdr clauses)))
        (if (cond-else-clause? first)
            (if (null? rest)
                (sequence->exp (cond-actions first))
                (error "ELSE clause isn't last -- COND->IF"
                       clauses))
            (make-if (cond-predicate first)
                     (sequence->exp (cond-actions first))
                     (expand-clauses rest))))))

Expressions (such as cond) that we choose to implement as syntactic transformations are called derived expressions. Let expressions are also derived expressions (see exercise 4.6).13

Exercise 4.2.  Louis Reasoner plans to reorder the cond clauses in eval so that the clause for procedure applications appears before the clause for assignments. He argues that this will make the interpreter more efficient: Since programs usually contain more applications than assignments, definitions, and so on, his modified eval will usually check fewer clauses than the original eval before identifying the type of an expression.

a. What is wrong with Louis's plan? (Hint: What will Louis's evaluator do with the expression (define x 3)?)

b. Louis is upset that his plan didn't work. He is willing to go to any lengths to make his evaluator recognize procedure applications before it checks for most other kinds of expressions. Help him by changing the syntax of the evaluated language so that procedure applications start with call. For example, instead of (factorial 3) we will now have to write (call factorial 3) and instead of (+ 1 2) we will have to write (call + 1 2).

Exercise 4.3.  Rewrite eval so that the dispatch is done in data-directed style. Compare this with the data-directed differentiation procedure of exercise 2.73. (You may use the car of a compound expression as the type of the expression, as is appropriate for the syntax implemented in this section.) .

Exercise 4.4.  Recall the definitions of the special forms and and or from chapter 1:

    and: The expressions are evaluated from left to right. If any expression evaluates to false, false is returned; any remaining expressions are not evaluated. If all the expressions evaluate to true values, the value of the last expression is returned. If there are no expressions then true is returned.

    or: The expressions are evaluated from left to right. If any expression evaluates to a true value, that value is returned; any remaining expressions are not evaluated. If all expressions evaluate to false, or if there are no expressions, then false is returned. 

Install and and or as new special forms for the evaluator by defining appropriate syntax procedures and evaluation procedures eval-and and eval-or. Alternatively, show how to implement and and or as derived expressions.

Writing SICP, since you never read it.

1 Name: Anonymous 2021-03-16 8:46

85 Name: Anonymous 2021-03-16 9:49

Name: Anonymous 2021-03-16 8:46

Name: Anonymous 2021-03-16 9:49