Sicp

Structure and Interpretation of Computer Programs Skill

Reference for fundamental programming concepts from Abelson and Sussman's "Structure and Interpretation of Computer Programs."

Activation Triggers

Use this skill when discussing:

• Procedural abstraction and higher-order functions
• Data abstraction and representation
• Recursion patterns (tree, tail, mutual)
• State, assignment, and environment model
• Streams and lazy evaluation
• Interpreters and metalinguistic abstraction
• Compilation and register machines

Quick Reference

Core Abstractions

| Abstraction | Purpose | Key Concept | |-------------|---------|-------------| | Procedural | Hide implementation details | Black-box abstraction | | Data | Separate use from representation | Constructors/selectors | | Syntactic | Create new languages | Interpreters/macros |

Higher-Order Function Patterns

| Pattern | Description | Example | |---------|-------------|---------| | Map | Transform each element | (map square list) | | Filter | Select matching elements | (filter even? list) | | Fold/Reduce | Accumulate to single value | (fold + 0 list) | | Compose | Combine functions | (compose f g) |

Recursion Patterns

| Pattern | Characteristics | Space | |---------|-----------------|-------| | Linear | Single recursive call | O(n) | | Tail | Result in recursive call | O(1) | | Tree | Multiple recursive calls | O(depth) | | Mutual | Functions call each other | Varies |

Data Structures

| Structure | Representation | Operations | |-----------|----------------|------------| | Pair | cons, car, cdr | Basic building block | | List | Chain of pairs | Sequence operations | | Tree | Nested pairs | Hierarchical data | | Set | List or tree | Union, intersection |

Evaluation Models

| Model | State | Binding | |-------|-------|---------| | Substitution | Stateless | Direct replacement | | Environment | Stateful | Frame-based lookup |

Stream Operations

| Operation | Behavior | Evaluation | |-----------|----------|------------| | cons-stream | Delay tail | Lazy | | stream-car | Get first | Immediate | | stream-cdr | Force tail | On-demand | | stream-map | Transform lazily | Lazy | | stream-filter | Select lazily | Lazy |

Directory Structure

sicp/
├── SKILL.md
├── procedures/
│   ├── abstraction.md
│   ├── higher-order-functions.md
│   └── recursion-patterns.md
├── data/
│   ├── data-abstraction.md
│   ├── hierarchical-data.md
│   └── symbolic-data.md
├── modularity/
│   ├── assignment-and-state.md
│   ├── environment-model.md
│   └── streams.md
└── metalinguistic/
    ├── interpreters.md
    ├── lazy-evaluation.md
    └── register-machines.md

Usage Examples

Designing Abstractions

Question: "How should I structure this complex function?"

Consider:
1. Identify primitive operations
2. Build compound procedures - See procedures/abstraction.md
3. Use higher-order functions - See procedures/higher-order-functions.md
4. Choose appropriate recursion - See procedures/recursion-patterns.md

Managing Complexity

Question: "How do I handle growing complexity?"

Consider:
- Data abstraction barriers - See data/data-abstraction.md
- Modularity through state - See modularity/assignment-and-state.md
- Lazy evaluation for infinite data - See modularity/streams.md

Building Languages

Question: "Should I create a DSL?"

Consider:
- Interpreter design - See metalinguistic/interpreters.md
- Lazy evaluation semantics - See metalinguistic/lazy-evaluation.md
- Compilation strategies - See metalinguistic/register-machines.md

---

Based on concepts from "Structure and Interpretation of Computer Programs" by Harold Abelson and Gerald Jay Sussman.

Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

• Author: grndlvl
• Source: grndlvl/software-patterns
• License: MIT

Install and usage instructions live in the source repository linked above.