Interlude: Church predecessor function with roses [1/2]
Recall that Church numerals are iterative appliers that take two arguments, a state transformer and an initial state. They work by repeatedly applying the state transformer to the current state, starting with the initial state. The number of applications performed by the Church numeral n is equal to the natural number n. One consequence is that the Church numeral zero returns the initial state unmodified. Another consequence is that given the Church numeral n, we can obtain the behavior of n+1 by letting n run the state transformer n times and then applying it one more time.
(define (zero state-transformer initial-state) initial-state)
(define empty "")
(define (addrose string) (string-append string "🌹"))
(zero addrose empty)
=> ""
(define (succ n) (lambda (state-transformer initial-state) (state-transformer (n state-transformer initial-state))))
((succ zero) addrose empty)
=> "🌹"
((succ (succ zero)) addrose empty)
=> "🌹🌹"
((succ (succ (succ zero))) addrose empty)
=> "🌹🌹🌹"
((succ (succ (succ (succ zero)))) addrose empty)
=> "🌹🌹🌹🌹"
((succ (succ (succ (succ (succ zero))))) addrose empty)
=> "🌹🌹🌹🌹🌹"Recall from SICP exercise 2.4 https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-14.html#%_thm_2.4 that pairs can be represented as invokers that take one argument, a receiver function. A pair works by invoking the receiver function with the two components of the pair as arguments. To extract the first component of the pair pass in the first projection as the receiver function, and to extract the second component pass in the second projection.
(define (make-pair a b) (lambda (receiver) (receiver a b)))
(define (first-projection a b) a)
(define (second-projection a b) b)
(define (first pair) (pair first-projection))
(define (second pair) (pair second-projection))
(first (make-pair "🌹" "🦋"))
=> "🌹"
(second (make-pair "🌹" "🦋"))
=> "🦋"In the same spirit we can define a box that holds a single element. The box works by invoking the receiver function with the content of the box as argument. To extract the content of the box pass in the identity function as the receiver.
(define (make-box a) (lambda (receiver) (receiver a)))
(define (identity a) a)
(define (extract box) (box identity))
(extract (make-box "🌹"))
=> "🌹"We can simulate the behavior of the Church numeral n using states in a box rather than naked states. We start by putting the initial state into a box, then at each step we extract the state from the current box, apply the state transformer and repack the result into a new box. At the end we have the result in a box, so we use a final extraction.
(define (make-repacker state-transformer) (lambda (box) (make-box (state-transformer (extract box)))))
(define (same-but-with-boxes n) (lambda (state-transformer initial-state) (extract (n (make-repacker state-transformer) (make-box initial-state)))))
((same-but-with-boxes (succ (succ (succ zero)))) addrose empty)
=> "🌹🌹🌹"This is not particularly useful yet because we are simulating n by using the n we already have in hand, but with two modifications this will change. First we look at the three steps of the repacker, extracting the state from the current box, applying the state transformer and repacking the result into a new box. The first two steps can be merged by passing the state transformer to the box. The box works by invoking the receiver function, in this case the state transformer, on the content of the box. This may look like a cosmetic change but the substance of it is that we are giving the box control over the application of the state transformer.
(define (make-merged-repacker state-transformer) (lambda (box) (make-box (box state-transformer))))
(define (same-again-but-with-boxes n) (lambda (state-transformer initial-state) (extract (n (make-merged-repacker state-transformer) (make-box initial-state)))))
((same-again-but-with-boxes (succ (succ (succ zero)))) addrose empty)
=> "🌹🌹🌹"