Quasiquoting in Scheme to Study a Computation

http://tobilehman.com/blog/2013/09/02/quasiquoting-in-scheme-to-study-a-computation/

 

 

Quasiquoting in Scheme to Study a Computation

Sep 2nd, 2013

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:

1 2 3 4 5 6 7

(define (fold-left op init seq) (define (iter result rest) (if (null? rest) result (iter (op result (car rest)) (cdr rest)))) (iter init seq))

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

1 2 3 4 5

(define (fold-right op first list) (if (null? list) first (op (car list) (fold-right op first (cdr list)))))

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

1 2 3 4 5

(fold-right / 1 (list 1 2 3)) ; => 3/2 (fold-left / 1 (list 1 2 3)) ; => 1/6

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:

1 2 3 4 5

(define a 2) (square a) ; value is 4 Evalutation '(square a) ; value is (square a) Quoting `(square ,a) ; value is (square 2) Quasiquoting

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).

1	(define (/ x y) `(/ ,x ,y)))

Then, recompute the values:

1 2 3 4 5

(fold-right / 1 (list 1 2 3)) ; => (/ (/ (/ 1 1) 2) 3) (fold-left / 1 (list 1 2 3)) ; => (/ 1 (/ 2 (/ 3 1)))

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.

Posted by Tobi Lehman Sep 2nd, 2013 scheme, sicp