stlog/posts/post01_continuations.skr

(post
 :title "Problem solving with Guile's prompts (call/cc)"
 :date (make-date* 2016 9 1)
 :tags '("guile" "prompts" "call/cc" "continuations")

 (h3 [(Also, first blog post!)])
 (p [Hello internets, thought I'd post some code I
           find interesting! Today, I want to introduce
           a really cool use case for Scheme's continuations. 
           While continuations are a neat scheme feature, I struggled to find examples
           showing their usefulness in everyday programming. While
           solving a project euler problem, though, I happened on a
           solution I think is elegant and not easily implemented
           without them (Please let me know if y'all have a solution).
           Please note that I am using Guile's prompts as a substitute
           for call/cc, which I will explain next time I update the page])
 (h3 [The problem:])
 (p [It is possible to show that the square root of two can be
        expressed as an infinite continued fraction.])
 (p [√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...])
 (p [By expanding this for the first two iterations, we get:])
 (p [1 + 1/2 = 3/2 = 1.5])
 (p [1 + 1/(2 + 1/2) = 7/5 = 1.4])
 (p [The eighth expansion, 1393/985, is the first example where the number
         of digits in the numerator exceeds the number of digits in the
         denominator.])
 (p [In the first one-thousand expansions, how many fractions contain
        a numerator with more digits than denominator?])
 (h3 [The solution:])
 (p [Okay, pretty easy answer structure: Build a list of the first
           1000 expansions, and filter those that pass the predicate.])
 (p [Very well, but what if, rather than find the first 1000
          expansions, the problem was stated this way:])
 (h3 [The problem, revised!])
 (p [Which expansion is the 500th example where the number of digits in
           the numerator exceed the number of digits in the denominator?])
 (h3 [Solution: revised!])
 (p [Since we don't know how many expansions we might enumerate before
           satisfying the predicate, we can't loop through a list of expansions like before.
           Instead, we need to continually test
           values until the predicate is satisfied.])
 (p [Generators can be useful here. Have a loop with three
                variables: an expansion generator, an index variable,
                and the current count of passed examples. We
                return the index when count >= 500.])
 (p [The difficulty here is implementing a generator for continued
         fractions. Unfortunately, it's not as easy to build as, say a
         fibonnaci generator, where the generator only needs to keep track
         of the two previous values. For a continued fraction generator,
         we need to remember the entire continued expasion, ie
         the FUNCTION STACK or CONTINUATION that produced the previous value!])
 (p [What we need is something that can capture the current
          function stack, add to it, save it, and then apply it to produce the next
          continued fraction. Guile prompts to the rescue! Using Guile's prompt
          primitives `call-with-prompt` and `abort-to-prompt` we write the following:])
 (code-block-scheme
  (car
   [(define (make-sqrt-2-generator) 
      (let ((*k* #f)                 ; current expansion
            (tag (default-prompt-tag)))
        (λ ()
          (call-with-prompt
            tag
            (λ ()
              (if *k*
                  (*k* (+ 2 (/ 1 (abort-to-prompt tag))))
                  (+ 1 (/ 1 (abort-to-prompt tag)))))
            (λ (k)
              (set! *k* k)
              (k 2))))))]))
 (p [This generator constructor does what we want: It defines the variable
          *k* whose value is the current expansion, and returns a generator
          procedure. Each time the generator is applied, our prompt builds
          the next expansion using the previous one, and then passes
          it as a continuation to our default prompt handler, which sets it to *k*, and applies it to return the value of the continued fraction.])
 (p [Testing our new generator we see it produces the correct values:])
 (code-block-scheme
  (car
   [(let ((generate-expansion (make-sqrt-2-generator)))
      (do ((i 0 (1+ i)))
          ((> i 5))
        (format #t "~a, " (generate-expansion))))
    
    => 3/2, 7/5, 17/12, 41/29, 99/70, 239/169]))
 (p [Now that we have a generator for square root convergent fractions,
         solving the problem straightforward!]))