/sicp

Structure and Interpretation of Computer Programs

Primary LanguageJavaScript

SICP - Structure and Interpretation of Computer Programs

Building Abstractions with Procedures

How ideas are made

  • Combining several simple ideas into one compound one, and thus all complex ideas are made.
  • The second is bringing two ideas, whether simple or complex, together, and setting them by one another so as to take a view of them at once, without uniting them into one, by which it gets all its ideas of relations.
  • The third is separating them from all other ideas that accompany them in their real existence: this is called abstraction, and thus all its general ideas are made.

Definitions

  • Computational process: Abstracts beings that inhabit computers
  • Progarm: Pattern of rules

Master software engineer

  • Ability to organize programs for intended results
  • Visualize system behaviour in advance
  • Structure programs to be easily debuggable

Well-designed systems

  • Modular
  • Parts can be separately
    • constructed
    • replaced
    • debugged

Programming in Lisp

  • Characterstics
    • Model of computation - recursive equations
    • Symbol manipulating capabilites for attacking programming problems i.e. symbolic differentiation and integration of algebric expression.
    • Data objects - atoms and lists
    • Second oldest language(only Fortran is older)
    • Lisp procedure can themselves be represented and manupulated as Lisp data.

The Elements of Programming

  • primitive expressions, which represent the simplest entities the language is concerned with
  • means of combination, by which compound elements are built from simpler ones
  • means of abstraction, by which compound elements can be named and manipulated as units.

Powerful programming language should be able to describe

  • primitive data
  • primitive procedure
  • combining and abstracting procedures and data

Compound Procedures

(define (<name> <formal parameters>) <body>)

Example:
(define (square x) (* x x))

Substitution Model

  • normal-order evaluation fully expand and then reduce
  • applicative-order evaluation evaluate the arguments and then apply

Conditional Expression and Predicates

(cond (<p1> <e1>)
      (<p2> <e2>)
      .
      .
      .
      (<pn> <en>))

(<p> <e>) == clause
 <p> == predicate
 <e> == consequent expression

Procedure as Black-Box Abstractions

  • It is crucial that each procedure accomplishes an identifiable task that can be used as a module in defining other procedures.
  • A user should not need to know how the procedure is implemented in order to use it.
  • Bound variable: procedures formal parameters(Body of procedure as their scope)
  • Free variables: variables not bound(external to definition) i.e <, -, +, custom procedure...
  • Internal definitions and block structure: nesting of definitions is called block structure. it helps in organizing the construction of large programs.

Procedures and the Processes They Generate

  • The ability to visualize the consequences of the actions under consideration is crucial to becoming an expert programmer
  • Deferred operation: expansion caused by process build up.
  • Recursive process: type of process where expansion occurs by a chain of deferred operations followed by contraction as the operations are actually performed.
  • Linear recursive process: A computation where the length of the chain of deffered operations, and hence the amount of information needed to keep track of it, grows linearly.
  • Iterative process: process whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an(optional) end test that specifies conditions usder which the process should terminate.
  • Contrast Iterative Vs Recursive:
    • In iterative case: the program variables provide a complete description of the state of the process at any point.
    • Iterative process can be stopped between steps and resumed with the value of the state variables.
  • Tail recursive: An implementation which executes an iterative process in constant space, even if the iterative process is described by a recursive procedure.

Tree Recursion

  • Counting Change: The number of ways to change amount a using n kinds of coin equals
    • The number of ways to change amount a using all but the first king of coin, plus
    • The number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin.
  • Divide into two groups
    • Those that do not use any of the first kind of coin, and
    • Those that do
  • Degenerate Cases
    • If a is exactly 0, we should count that as 1 way to make change.
    • if a is less than 0, we should count that as 0 ways to make change.
    • If n is 0, we should count that as 0 ways to make change.

Orders of Growth

  • In general there are a number of properties of the problem with respect to which it will be desirable to analyze a given process