SICP series (part 1) : the substitution model
Introduction:
I recently dove into the famous 'Structure and Interpretation of Computer Programs' (SICP), aka the Wizard Book. I thought it'd be cool to share what I'm learning in a blog series about the big ideas from the book that I didn't know before or didn’t put a name on those.
SICP is all about the core principles of computer science, and it uses Scheme, a language cooked up by Gerald Jay Sussman (one of the authors) and Guy L. Steele, for all its coding examples. Scheme is like a mix of Lisp and Algol, so get ready for lots of parentheses. In the first part of the article, I'll break down the bare minimum of Scheme we need to get what's going on, especially when it comes to the substitution model.
How to Create a Procedure in Scheme (Function)?
Here is a procedure that adds two numbers together:
1
2
(define (add n1 n2)
(+ n1 n2))
The define keyword is used to create a procedure or a variable. In the case of a procedure, the first pair of parentheses is used to define the name of the procedure (add) and the parameters of the procedure (n1 and n2). The second pair represents the body of the procedure ((+ n1 n2)). Unlike in JavaScript or Java, there is no need for a return keyword. Whatever is at the end of the procedure will be automatically returned.
You may have also noticed that the + is before the numbers and not between them. This is called prefix notation, where the operator is written first, followed by the operands. I'll show you some examples:
1
2
3
(+ 1 2 3) ; 6
(< 1 0) ; true
Lastly, I'll demonstrate how to call a procedure in Scheme:
1
(add 5 9) ; 14
And I think that with that we are good to explore what is the substitution model.
What is the substitution model ?
The substitution model is a method for comprehending how a procedure functions by breaking it down step by step. At each step, we aim to simplify the procedure to its most primitive values (when the only thing left is the operator and the operands). Let's illustrate this with an example using our add function:
1
2
3
4
(define (square n)
(* n n)) ; Note: Scheme has a built-in square procedure, but we redefine it here to avoid confusion
(square (add (add 1 2) (add 2 3)))
Using the definition of add, this reduces to:
1
(square (add (+ 1 2) (+ 2 3)))
Continuing the reduction:
1
(square (add 3 5))
Further simplifying:
1
(square (+ 3 5))
Progressing through the reduction steps:
1
(square 8)
Finally:
1
(* 8 8)
And we arrive at the result: 64.
The substitution model provides a helpful framework for thinking about procedure application. It's essential to note that this is a conceptual tool for understanding, and it doesn't precisely mirror how the Scheme interpreter operates in reality.
Normal Order, aka Lazy Evaluation:
When we performed the substitution earlier, at each step, we evaluated the operator and operands, executing the computation of the operator on the operands. This model is known as "applicative order," but it's not the only evaluation strategy. Another model, called "normal order," defers the computation until it's absolutely necessary. This approach is employed in languages like Haskell and in Java streams.
Let's revisit our last example and redo the substitution, this time using the normal order:
1
(square (add (add 1 2) (add 2 3)))
No difference so far:
1
(square (add (+ 1 2) (+ 2 3)))
Here, we begin to delay the computation of (+ 1 2) and (+ 2 3):
1
(square (+ (+ 1 2) (+ 2 3)))
We reach a point where, in the next steps, we are compelled to perform the computations to proceed:
1
(* (+ (+ 1 2) (+ 2 3)) (+ (+ 1 2) (+ 2 3)))
Performing the computations:
1
2
3
(* (+ 3 5) (+ 3 5))
(* 8 8)
Finally, we obtain the result: 64.
As observed, there are more evaluations involved with the normal order evaluation than with the applicative order evaluation. This is why Scheme, and most programming languages, use applicative order to avoid unnecessary evaluations.
If you didn't catch it, let me highlight the difference in evaluations between the two models. In the applicative order example, the evaluation (+ (+ 1 2) (+ 2 3)) is performed once. In the normal order example, this evaluation is performed twice: (* (+ (+ 1 2) (+ 2 3)) (+ (+ 1 2) (+ 2 3))).
While normal order is typically less efficient, don't dismiss it too quickly it can be an invaluable tool for constructing infinite data structures like streams. There are also cases where normal order is more efficient; for instance:
1
2
3
(define (square-if-more-than-100 n)
(if (< n 100) n
(square n)))
If the substitution is done with applicative order, the square computation will still be performed for a number less than 100, but not with normal order.
Conclusion:
In this article, we explored Scheme and delved into the substitution model, examining both the applicative order and the normal order of applying substitution. Stay tuned for my next blog posts on the SICP series, where we'll likely delve into the differences between recursive procedures and recursive processes, as well as the different types of recursive processes.