Practicing SICP Data-Directed Programming in Haskell

SICP (Structure and Interpretation of Computer Programs) is widely regarded as a classic textbook in computer science. Chapter 2 of this book delves deeply into methods of data abstraction, particularly focusing on the concept of data-directed programming in section 2.4.3. The article on Lobsters by entropicthoughts.com, authored by kqr, introduces an attempt to implement this concept in Haskell.

SICP and the Data-Directed Approach

Written by Abelson and Sussman and published by MIT Press in 1996, SICP is affectionately known as the “Wizard Book” and has had a profound impact on many programmers. Given the book’s vast content, fully comprehending every detail is no small feat, so the author adopts an approach of focusing on specific sections of interest.

In a previous article, the implementation of tagged data in Haskell was discussed. However, the authors of SICP did not consider tagged data to be the optimal approach. This is because every time a new data representation is added, it necessitates modifying all existing operations. To address this issue, they propose the data-directed programming approach.

Four Operations for Complex Numbers

Complex numbers can be represented in two forms: rectangular coordinates (real and imaginary parts) and polar coordinates (magnitude and angle). Regardless of the representation, four quantities must be retrievable from complex numbers:

• Real part in rectangular coordinates
• Imaginary part in rectangular coordinates
• Magnitude in polar coordinates
• Angle in polar coordinates

In the previous implementation using tagged data, functions inspected tags to select the appropriate representation. While this method works, adding a new representation requires modifying all four operation functions, which is cumbersome.

Limitations of Tagged Data

In the tagged data approach, type tags are added as follows:

attach_tag tag contents = (tag, contents) 
type_tag (tag, _) = tag 
contents (_, value) = value 

To distinguish between rectangular and polar representations, tag strings are compared:

is_rectangular z = type_tag z == "rectangular" 
is_polar z = type_tag z == "polar" 

make_rectangular re im = (attach_tag "rectangular" (re, im)) 
make_polar r a = (attach_tag "polar" (r, a)) 

The main issue with this method is the need to add conditional branches to all existing operation functions whenever a new representation format is introduced. This violates the Open/Closed Principle of design.

The Core of Data-Directed Programming

The data-directed approach proposed by Abelson and Sussman involves implicitly declaring an operations table and using two functions, get and put, to retrieve and store operations.

In Haskell, this can be implemented using the State monad as follows:

put op tag fn = State.modify (Map.insert (op, tag) fn) 
get op tag = State.gets (Map.lookup (op, tag)) 

This table allows the installation of operations for rectangular representations:

install_rectangular = do 
 put "real_part" "rectangular" (\(re, _) -> re) 
 put "imag_part" "rectangular" (\(_, im) -> im) 
 put "magnitude" "rectangular" (\(re, im) -> sqrt (re^2 + im^2)) 
 put "angle" "rectangular" (\(re, im) -> atan2 im re) 

Similarly, operations for polar representations can be installed:

install_polar = do 
 put "real_part" "polar" (\(r, a) -> r * cos a) 
 put "imag_part" "polar" (\(r, a) -> r * sin a) 
 put "magnitude" "polar" (\(r, _) -> r) 
 put "angle" "polar" (\(_, a) -> a) 

Advantages of the Data-Directed Approach

The greatest advantage of this approach lies in the fact that adding a new representation format does not require modifications to existing code. Simply installing new operations for the new representation ensures that existing generic operations can automatically handle the new format.

SICP’s text further elaborates on a mechanism using a generic application function, apply_generic, which looks up the appropriate implementation from the operations table based on the operation name and data.

Implications for Software Design

Data-directed programming offers important insights for modern software design. Many contemporary design patterns, such as plugin architecture, dependency inversion, and strategy patterns, have evolved from these ideas.

In functional programming languages like Haskell, ad-hoc polymorphism using type classes is widely employed as an alternative to the data-directed approach. However, while type classes resolve operations at compile time, data-directed programming dispatches operations at runtime, offering greater flexibility for systems requiring dynamic extensions.

For instance, systems like agent-skills for teaching development processes to AI agents could benefit from the design principles of a pluggable operations table. In such systems, the ability to add new skills to an agent without modifying existing implementations makes the data-directed approach a valuable design choice.

Editorial Opinion

The Haskell implementation of data-directed programming serves as an excellent example of how classical textbook ideas can be embodied in modern functional programming languages. In the short term, this implementation can aid Haskell programmers studying SICP in understanding the transition from tagged data to the data-directed approach. Furthermore, in existing Haskell codebases, where dynamic extensibility is required but challenging to express with type classes, this approach may serve as a viable alternative.

In the long term, the philosophy behind data-directed programming continues to influence modern software architecture. Systems like plugin frameworks, microservices with service discovery, and routing tables are all underpinned by the same principles. Methods for achieving dynamic dispatch while maintaining Haskell’s type safety will likely evolve into more refined forms.

As an editorial note, the question of when to choose between type classes and the data-directed approach in functional programming remains an open discussion.

References

• “Data-directed programming in Haskell (SICP2.4.3)”, by entropicthoughts.com by kqr — Lobsters, 2026-07-12T09:07:07.000Z (ARR)
• Source URL: https://entropicthoughts.com/sicp-2-4-data-directed-programming-in-haskell