tobilehman.com: a blog on computing, structure and math

# Quasiquoting in Scheme to Study a Computation

While working though Structure and Interpretation of Computer Programs, I came across the definition of the fold-right function:

Exercise 2.38: The accumulate procedure is also known as fold-right, because it combines the first element of the sequence with the result of comining all the elements to the right.

I have trouble with purely verbal explanations of things, I prefer notation and diagrams whenever appropriate. In exercise 2.38, the authors give a definition of fold-left in Scheme:

And using fold-right (accumulate) from earlier in the text:

To show that fold-left and fold-right are different, the authors ask for the values of:

However, that does not show why they are different. To get a better understanding of why these functions are different, I used a feature of Scheme called quasiquoting, it’s similar to quoting, but allows for partial evaluation, I’ll explain with an example:

Quoting returns the expression itself, not the value it evaulates to. Quasiquoting returns the expression itself, after evaluating all the expressions after commas.

So, to study the (fold-right / 1 (list 1 2 3)) and (fold-left / 1 (list 1 2 3)) computations, we can redefine / to use quasiquoting, and prevent the scheme interpreter from evaluating it all the way down to a number. Instead of (/ 1 2) evaluating to 1/2, we want it to evaluate to (/ 1 2).

Then, recompute the values:

This expanded view makes it very clear how these functions are different. It also suggests that they are different only for non-associative operators.

Here’s another example of quasiquoting that is useful for visualizing the recursive structure of a computation.