Planet Scheme

October 01, 2014

Ben Simon

Gotcha of the Day: Gambit Scheme App's Script Panel is Blank

I kept running into this odd issue with the Gambit for Android app. When I first kicked off the app I got this nice splash screen:

I could then switch to the Scripts section to see various examples. I then added my own lex helper function. After adding it, I'm able to switch back to the REPL and see that it works:

So far, so good. When I'd kick off Gambit again, I'd be taken right to a basic REPL screen. But when I used the menus to switch to the Scripts section I was consistently taken to a blank screen:

What the heck? Where'd the scripts go?

I let the app just sit for a while - maybe it was hung on something. Then I forced it to stop and restarted it. Again, still blank. Then I rebooted the phone. Again, still blank. Finally, I uninstalled and re-installed the app. That fixed the problem. That is, until the problem popped back up again. Again, what the heck?

As a work around, I found that if I cleared the app's data I'd effectively reset the app back to the starting start; the splash screen appears, but my custom script is gone.

Surely there had to be a better way.

Then I took a closer look at the sample scripts. I noticed that the 'main' script is as follows:

;; Main script.
;;
;; Start with splash screen.

(splash)

I switched to the REPL and entered the code (splash). What do you know, the splash screen appeared!

Looking closer at the sample scripts I also noticed calls to (repl) and (edit). Invoking these functions switch you to the REPL and to the script editing screen respectively.

I think I get what the app is doing. I told it to run my little script. And it's doing exactly that. I'm not setting up the edit screen, so switching to the edit panel in the menu system isn't working. I think that's probably a bug in the app, but a fairly minor one. For one, I can switch to the edit screen anytime I want by invoking (edit) and for another, if I update my script to read:

(define (lex)
  (load "/sdcard/Documents/ex1.scm"))

(edit) ; ****

Then every time Gambit starts, it begins in the edit Scripts instead of a plain o' REPL. At the end of the day, I need to give the Gambit App more credit, it's actually doing something pretty slick.

by Ben Simon (noreply@blogger.com) at October 01, 2014 11:26 AM

September 30, 2014

Ben Simon

repl.it - Love It! And Learn to program with two URLs

This morning I worked up a solution to today's Programming Praxis challenge (find it here). The code was simple enough to write (and yes, I wrote it on my Galaxy S5). A few minutes after I committed the solution to git, I decided I wanted to tweak a function name.

Github provides an easy enough way to edit a file and commit the change. The catch is that I know from countless goofs that even the most trivial change needs to be checked before committing. I could fire up my Android Scheme Dev environment without much difficulty, but at the time, I had a Firefox window open to Github on my Laptop. It occurred to me: surely there had to be an online Scheme REPL I could test my fix with. Then I wouldn't have to leave my browser (much less my dev environment).

I give you repl.it. Here's my fix in action:

Now I know this snippet of code was pretty trivial, but still, I'm floored by how impressive repl.it is. As an educational tool, it's nothing short of amazing. All you need is a web browser and some time, and you can be on your way to learning how to program.

repl.it isn't limited to Scheme dev either. Of particular note is the presence of a Forth interpreter, which is another language I enjoy puttering around with.

OK Ladies and Gentlemen, ready to learn to program? Here are the two URLs you're going to need:

  1. Structure and Interpretation of Computer Programs (SICP). Depending on who you ask, it's either the greatest text ever written on the topic of programming, or absolute junk. I belong to the former camp.
  2. repl.it. Don't just read SICP, execute it. Run the code. Solve the examples. repl.it seems powerful enough to do just that.

So stop surfing, and start learning!

by Ben Simon (noreply@blogger.com) at September 30, 2014 02:31 PM

Programming Praxis

Thue-Morse Sequence

Mathematicians are strange people. As an example, I offer the Thue-Morse sequence, which is a binary sequence of 0’s and 1’s that never repeats, obtained by starting with a single 0 and successively appending the binary complement of the sequence. Thus, term 0 of the sequence is (0), term 1 of the sequence is (0 1), term 2 of the sequence is (0 1 1 0), term 3 of the sequence is (0 1 1 0 1 0 0 1), term 4 of the sequence is (0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0), and so on; to calculate term 3 from term 2, we started with term 2 (0 1 1 0), complemented each element of the term (1 0 0 1), then appended the two (0 1 1 0 1 0 0 1). That looks useless to me, but mathematicians have been excited by it since 1851, hence my conclusion that mathematicians are strange people.

Your task is to write a program that generates the nterm of the Thue-Morse sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at September 30, 2014 09:00 AM

September 29, 2014

Jeremy Kun

Making Hybrid Images

Leonardo da Vinci’s Mona Lisa is one of the most famous paintings of all time. And there has always been a discussion around her enigmatic smile. He used a trademark Renaissance technique called sfumato, which involves many thin layers of glaze mixed with subtle pigments. The striking result is that when you look directly at Mona Lisa’s […]

by Jeremy Kun at September 29, 2014 03:00 PM

Ben Simon

More Scheme Dev on Android, Now With Git Support

Continuing on my Scheme on Android kick, here's a solution to the most recent Programming Praxis problem. It's actually quite an interesting challenge:

It is generally accepted wisdom that people should use different passwords for each of their online accounts. Unfortunately, few people do that because of the difficulty of remembering so many passwords.

Manuel Blum — he’s the guy in the middle of the Blum Blum Shub sandwich — suggests an algorithm that hashes a web site name into a password. Further, his algorithm is cryptographically secure, so no one else can determine your password, and can be worked mentally, without a computer or even pencil and paper.

Read more about the algorithm here. I don't have the mental muscle to execute the hash in my head, but it was a terrific little coding challenge.

I used the same setup as last time: Gambit Scheme + DroidEdit + Perixx 805L Keyboard. For the most part, I found myself writing and executing Scheme with little regard for the fact that I was working on a cell phone. That, of course, is what I'm after.

Two improvements I've made in the setup:

First, I've defined a procedure named lex, which I can invoke to reload the source file I'm working on:

This combined with a couple of keyboard shortcuts to switch between Gambit and DroidEdit means that I can modify, reload and execute new code with relative ease. Having the source code live in ex1.scm means that the entire solution to the problem will be in one file. Which for the purposes of developing solutions to these brain teasers is ideal.

Second, I've setup git in Terminal IDE. So now, when I'm finished developing a solution, I can archive it. DroidEdit has built in support for Git, but I prefer a command line interface to version control.

Setting up Terminal IDE took just a bit of wrangling. Here's what I did:

  • Made sure the appropriate public key was in Github.
  • On a Linux machine that had the dropbear ssh tools installed, I converted my private key to be in the dropbear format:
    mkdir ~/tmp/working
    cp ~/.ssh/id_dsa ~/tmp/working
    cd ~/tmp/working
    ssh-keygen -p -f id_dsa # strip the encryption from the openssh key
    dropbearconvert openssh dropbear id_dsa id_dsa.db
    # Copy id_dsa.db to the Galaxy S5
    rm -rf ~/tmp/working
    
  • Checked the key on my phone by running the following within Terminal IDE:
    ssh -i id_dsa.db git@github.com
    
  • Within Terminal IDE, I created a wrapper script named gitssh to launch ssh properly:
    #!/data/data/com.spartacusrex.spartacuside/files/system/bin/bash
    ssh -i $HOME/id_dsa.db $*
    
  • Still within Terminal IDE, I set the GIT_SSH variable to the above script:

    setenv GIT_SSH=gitssh
    
  • I was then able to launch git commands as usual:
     git clone ssh://git@github.com/benjisimon/code
     ...
    

Happy on the go hacking!

by Ben Simon (noreply@blogger.com) at September 29, 2014 12:13 PM

September 26, 2014

Programming Praxis

Blum’s Mental Hash

It is generally accepted wisdom that people should use different passwords for each of their online accounts. Unfortunately, few people do that because of the difficulty of remembering so many passwords.

Manuel Blum — he’s the guy in the middle of the Blum Blum Shub sandwich — suggests an algorithm that hashes a web site name into a password. Further, his algorithm is cryptographically secure, so no one else can determine your password, and can be worked mentally, without a computer or even pencil and paper.

Blum’s algorithm works in two steps. A function f maps letters to digits, and a permutation g transposes the digits. The two, taken together, form your personal key, and so must be kept secret.

The first step maps letters to digits; since there are more letters than digits, some of the digits are used more than once. If, for instance, f(a) = 8, f(b) = 3, and f(c) = 7, then the first step would map the input “abc” to the digits [8, 3, 7].

The second step uses the permutation g to calculate the output. Begin with the first and last digits, adding them mod 10; in the example, (8 + 7) % 10 = 5. If the permutation g = 0298736514, then the next digit after 5 is 1, so the first output digit is 1.

After that, each remaining input digit is the basis of an output digit. Calculate the sum of the next input digit and the previous output digit, mod 10, and take the next digit of the permutation, repeating for each remaining input digit. In the example, the second input digit and the first output digit are summed mod 10, (3 + 1) % 10 = 4, and the next digit in the permutation is 0 (wrapping around), so the second output digit is 0. In the same way, the third output digit takes the third input digit and the second output digit, sums them mod 10, and computes the permutation, so (7 + 0) % 10 = 7, which permutes to 3. So the final password produced from an input of “abc” is “103”.

Your task today is to implement Manuel Blum’s mental hashing algorithm for mapping a web site name to a password. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at September 26, 2014 09:00 AM

September 25, 2014

Greg Hendershott

Written in Racket

This is an overview of things I’ve created using Racket. Two motivations for writing this now:

  1. Over the last week I was at three conferences (whew!) where, when meeting or catching up with someone, I had to explain what I’ve been doing. I mentioned my current projects or projects I guessed they’d relate to. But that’s not necessarily representative of all that I’ve been able to do with Racket. I wish I’d been able to give a better overview. I have quite a few repos on GitHub, but that’s just a big list with no structure.

  2. In about a week I start my batch at Hacker School. I’ll likely spend less time with Racket, because the whole point is to learn new things. Now is a good time to take inventory. And I’ll be better prepared to talk about Racket there.

As a result, here’s an inventory, grouped into categories.

Web services

I wrote a wrapper for most of the Amazon AWS web services. Working with AWS directly at the HTTP level is really fun and educational. Well. It’s fun when writing a wrapper library. Not so fun when writing an app. Hence a wrapper library.

To support aws, I made a small http library to help with things like 100-continue responses, chunked transfer decoding, and so on.

I made an interface to Google API Discovery Service. This was fun because I didn’t hand write wrapper code. Instead, I query this Google web service that describes their web services. Racket macros use that response data to create wrapper functions. I even generate Scribble documentation.

More generally, webapi-markdown is a way I came up with to do “literate” (in the sense of “literate programming”) web API specifications. A web service is both documented and specified using a markdown file containing parameterized HTTP request and response templates. wffi (think “web foreign function interface”) is an implementation for Racket.

When I was grumpy with Google for killing Google Reader, I wrote feeds2gmail, which is similar to the venerable rss2email, but:

  • Creates emails directly in your mailbox using IMAP APPEND (faster and no delivery issues).

  • Uses two IMAP mailboxes — Gmail “labels” — to be a bit closer to the GReader experience.

Static blogging and markdown parsing

My most-starred project on GitHub is Frog. Making a static blog generator isn’t very special. But Frog is special among my Racket projects because it’s an application, not a library or programming tool. I wanted something that was much easier and simpler to install and use than Octopress. To the extent that succeeded, it’s largely due to the choice of using Racket.

As I blogged about, the hardest part of that project was parsing markdown. I ended up using a monadic parser combinator approach, very similar to how Pandoc does this. (Later I used the same approach to whip up a toml parser.)

A racket mode for Emacs

Although a big chunk of racket-mode is obviously Emacs Elisp, most of the more challenging and interesting bits are actually written in Racket. Such as:

  • Given a symbol, how do you find the definition site? How do you extract its “signature” and/or contract and/or Typed Racket type? How do you find its installed documentation, if any?

  • How do you let people write programs using racket/gui, but not make everyone pay the cost of loading it and popping up a racket frame window all the time? In other words, how do you do an on-demand, one-time initializiation of racket/gui?

  • And so on.

I hope I have time to blog more about this.

Some Clojure idioms for Racket

I have a few “armchair” languages. I’ve read a lot about them, read quite a bit of code, but not yet written much myself. At the moment these include Haskell and Clojure. During my time at Hacker School I expect to move these out of the armchair category.

Meanwhile, I learned enough about Clojure to like a few of its ideas or idioms and want to use them in Racket. The result, with contributions from some other people, is rackjure.

A few features — such as applicative dictionaries, curly brace dictonary literals, and function literals — must be used as a Racket language: #lang rackjure. The remaining features can be required as needed.

Things not on GitHub

I did a few things that I didn’t put on GitHub. Yeah, I know. Code or it didn’t happen. Regardless….

Signal processing

I experimented with signal processing combinators (including but not limited to audio signal processing).

Why isn’t this on GitHub?

  1. It’s just proof-of-concept, playing with signals being functions from time to a value. (Pleasant surprise: This turned out to be much more performant for audio processing than I expected.)

  2. Eventually I realized I was starting to reinvent aspects of FRP; maybe I should back up and learn from others.

  3. It was a chance for me to try Typed Racket. With great results: Typed Racket made my code less buggy and faster, both. I could specify specific vs. generic signals — e.g. (Signal Float) vs. (Signal a).

  4. My background is the music tech industry. I’m leery of people’s expectations. (“Isn’t it cute, the monkey thinks it can write professional audio DSP code.”)

Web app middleware framework

“Lob” is a low-level library for web applications, in the spirit of Python’s WSGI, Ruby’s Rack, and Clojure’s Ring. Like those, Lob is intended to be the glue between a web server and a higher-level web application framework.

Although I was pretty happy with how this turned out, I wasn’t using it actively in a real world project. It’s one thing to dogfood a project and support other people using it for similar use cases. But it’s another thing to, well, not do that. So… not on GitHub.

Writing about Racket

I wrote Fear of Macros, which is a sort of autobiographical tutorial for Racket macros. Although it’s probably not the best introduction for everyone, it might help people like me.1

I’ve written some blog posts.

I’ve tried to pull my weight on the Racket user mailing list and on Stack Overflow — it’s fun as you gradually gain confidence to help others the way you were helped. I find it’s also a great test whether I really understand something as well as I imagined.


All other

I think that sums up nearly everything I’ve made into a repo on GitHub, or even an actual Racket package for others to use.

Of course I’ve tried many more things in Racket, that I have sitting around here and there. Web crawling and scraping. Alternative definition forms. And more. All have been fun to do, and most have taught me more about Racket and/or programming in general.


  1. Macros might be one of those subjects — like continuations or monads? — where people need to read a few introductions until one “clicks” for them. I suppose the common theme among these things is that they tend to get mythologized and jargonized. Some of us need to take a deep breath, see how the underlying mechanism is actually quite simple, and build up from there. 

by Greg Hendershott at September 25, 2014 10:14 AM

September 24, 2014

Ben Simon

Are we there yet? Writing and Running Scheme Code on Android

Here's the solution to the most recent Programming Praxis problem. It's not the most pithy or elegant code, but it gets the job done:

; Solution to: http://programmingpraxis.com/2014/09/23/triangle-roll-up/
(define first car)
(define second cadr)

(define (sum row)
  (let loop ((row row) (result '()))
    (if (= (length row) 1)
        (reverse result)
        (loop (cdr row)
              (cons (+ (first row) (second row))
                    result)))))
                    
(define (roll numbers)
  (let loop ((numbers numbers) (result (list numbers)))
    (cond ((< (length numbers) 2)
           (reverse result))
          (else
           (loop (sum numbers) (cons (sum numbers) result))))))
           
 (define (fmt results)
   (for-each (lambda (r)
               (display r)
               (newline))
              (reverse results)))

> (fmt (roll '(4 7 6 3 7)))
(87)
(46 41)
(24 22 19)
(11 13 9 10)
(4 7 6 3 7)

One reason it's not streamlined: I worked out the solution on my Galaxy S5. As a Schemer at heart, I've always wanted to have a Scheme interpreter running on my phone . Unfortunately, I've never found an environment robust enough to be anything more than a basic demo.

But times change, so I figured it was worth checking the Play Store for new Scheme options.

To my delight I found quite a few. There's Scheme REPL, Scheme Droid, Gambit and Scheme Pad. They're all very promising. I figured trying to solve the Programmin Praxis problem would be an ideal test. Note, I'm using my Perixx 805L Keyboard for text entry. None of these environments would be of any use without an external keyboard. As usual, the Perixx worked really well. (Allowing me to develop a Scheme solution and compose this blog entry.)

Casually browsing through the apps, Scheme Pad looked most promising. It had a way to load and save files and included parenthesis matching. Paren matching is absolutely key. Unfortunately, Scheme Pad is too smart for its own good. It tries to automatically send lines of code to the REPL as you enter them, and I quickly found that I could confuse the app. When it works, it's awesome, but I found myself having to load and reload my example file to keep it working.

Back to the drawing board.

When I went back to the apps, I was pretty bummed out. None of them had the paren matching Scheme Pad had, so they really weren't going to be realistic solutions.

Then I thought I'd take another approach. What if I used an external text editor to do the authoring of the scheme file and just used one of the REPLs to interpret it.

After a couple of false starts I found Droid Edit, which is quite the impressive editor. It does paren matching, text highlighting, and responds to keyboard short cuts. I'll almost certainly be buying the pro version to get rid of the ad in the bottom right hand corner.

I found that I was able to scratch out some Scheme code without any difficulty. I could then flip over to the Gambit REPL and load in my file:

(load "/sdcard/Documents/ex1.scm")

The Gambit App allows you to scroll back in the REPL and hit enter on a previously run expression. This queues up the expression for you to edit and run. The result is that I had to type my load command once and then could re-run it.

The edit, Alt-Tab, load, run, loop isn't quite the most efficient way to program. But, both the editor and REPL are excelling what they do, so it seems reasonable to put up with the two app solution.

Not to mention, I'm fairly certain I could automate the process further by using the External Keyboard app's shortcuts or perhaps using Tasker.

Here's some screenshots of the development in action:



I think it'll take a bit more tweaking, but it does seem that a Scheme environment that Really Works is achievable on Android.

Whoo!

by Ben Simon (noreply@blogger.com) at September 24, 2014 02:55 PM

September 23, 2014

Programming Praxis

Triangle Roll-Up

We have a simple little exercise today: Given a list, write a triangle showing successive sets of sums of the pair-wise elements of the list. For instance, given the input 4, 7, 3, 6, 7, your program should write this output:

81
40 41
21 19 22
11 10 9 13
4 7 3 6 7

The original list is at the bottom of the triangle. The next row up has pair-wise sums of the elements of the list: 4 + 7 = 11, 7 + 3 = 10, 3 + 6 = 9, and 6 + 7 = 13. The next row up has pair-wise sums of those list elements: 11 + 10 = 21, 10 + 9 = 19, and 9 + 13 = 22. The next-to-top row has only two sums: 21 + 19 = 40 and 19 + 22 = 41. And finally the top row is the sum of those two numbers: 40 + 41 = 81.

Your task is to write a program to print the triangle roll-up of an input list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at September 23, 2014 09:00 AM

September 22, 2014

Joe Marshall

A couple more homographic function tricks

A generalized continued fraction is an expression of the form:
You can partly apply a homographic function to a generalized continued fraction if you have a stream of the ai and bi
(define (partly-apply-general hf nums dens)
  (let ((a (first  hf))
        (b (second hf))
        (c (third  hf))
        (d (fourth hf)))
    (if (empty-stream? nums)
        (values (list a a
                      c c)
                nums
                dens)
        (let ((num (head nums))
              (den (head dens)))
          (values (list (+ (* a den) (* b num)) a
                        (+ (* c den) (* d num)) c)
                  (tail nums)
                  (tail dens))))))

(define (print-hf-general hf nums dens)
  (call-with-values (lambda () (partly-evaluate hf))
    (lambda (term hf*)
      (if (not term)
          (call-with-values (lambda () (partly-apply-general hf nums dens))
            print-hf-general)
          (begin
            (display term) 
            ;; take reciprocal and multiply by 10
            (let ((a (first hf*))
                  (b (second hf*))
                  (c (third hf*))
                  (d (fourth hf*)))
              (print-hf-general (list (* c 10) (* d 10)
                                      a        b)
                           nums dens)))))))
For example, we can compute pi from this generalized continued fraction:
(print-hf-general (list 0 4 1 0)
              ;; [1 1 4 9 16 25 ...]
       (cons-stream 1
      (let squares ((i 1))
    (cons-stream (* i i) (squares (1+ i)))))
              ;; [1 3 5 7 9 11 ...]
       (let odds ((j 1)) 
     (cons-stream j (odds (+ j 2)))))

314159265358979323846264338327950^G
; Quit!
A bi-homographic function is a function of the form:
(define (bi-homographic a b c d e f g h)
  (lambda (x y)
    (/ (+ (* a x y) (* b x) (* c y) d)
       (+ (* e x y) (* f x) (* g y) h))))
Like a homographic function, you can partly evaluate a bi-homographic function and generate a continued fraction. You can also partly apply a bi-homographic function to a pair of continued fractions. When you do this, you have a choice of which continued fraction to be the object of the partial application. There's about twice as much nasty math involved, but the gist is that a bi-homographic function takes two continued fractions as arguments and produces one continued fraction as a result.

It turns out that addition, subtraction, multiplication and division are bi-homographic functions, so one can incrementally compute sums and products of continued fractions.

by Joe Marshall (noreply@blogger.com) at September 22, 2014 11:49 PM

Alaric Snell-Pym

Recent Ugarit progress

I had some time to work on Ugarit yesterday, which I made good use of. I really should have worked on raw byte-stream-level performance issues - I did a large extract recently, and it took a whole week - but, having a restricted time window, I caved in and did something fun instead; I started […]

by alaric at September 22, 2014 04:06 PM

September 21, 2014

Grant Rettke

Announce: PicoLisp in Hardware (PilMCU)

PilMCU is an implementation of 64-bit PicoLisp directly in hardware. A
truly minimalistic system. PicoLisp is both the machine language and the
operating system:

Via help-gnu-emacs.

by Grant at September 21, 2014 01:18 AM

September 19, 2014

Jeremy Kun

Occam’s Razor and PAC-learning

So far our discussion of learning theory has been seeing the definition of PAC-learning, tinkering with it, and seeing simple examples of learnable concept classes. We’ve said that our real interest is in proving big theorems about what big classes of problems can and can’t be learned. One major tool for doing this with PAC is the concept of VC-dimension, but […]

by Jeremy Kun at September 19, 2014 03:00 PM

Programming Praxis

Diophantine Reciprocals

Career Cup claims that Amazon asked this as an interview question; it is also Problem 108 at Project Euler:

In the following equation x, y and n are positive integers: 1 / x + 1 y = 1 / n. For n = 4 there are exactly three distinct solutions: 1/5 + 1/20 = 1/6 + 1/12 = 1/8 + 1/8 = 1/4. What is the least value of n for which the number of distinct solutions exceeds one thousand?

Your task is to solve Amazon’s question; you might also like to make a list of the x, y pairs that sum to a given n. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at September 19, 2014 09:00 AM

September 18, 2014

Joe Marshall

A useful, if somewhat pointless, trick with homographic functions

In my previous posts I showed that if you are applying a homographic function to a continued fraction, you can partly evaluate the answer before you completely apply the function. Instead of representing homographic functions as lambda expressions, I'll represent them as a list of the coefficients a, b, c, and d in (lambda (t) (/ (+ (* a t) b) (+ (* c t) d))). I'll represent a simple continued fraction as a stream of the integer terms in the denominators.
Here is how you partly apply a homographic function to a continued fraction:
(define (partly-apply hf cf)
  (let ((a (first  hf))
        (b (second hf))
        (c (third  hf))
        (d (fourth hf)))
    (if (empty-stream? cf)
        (values (list a a
                      c c)
                cf)
        (let ((term (head cf)))
          (values (list (+ (* a term) b) a
                        (+ (* c term) d) c)
                  (tail cf))))))
Partly evaluating a homographic function involves looking at the limits of the function as t starts at 1 and goes to infinity:
(define (partly-evaluate hf)
  (let ((a (first hf))
        (b (second hf))
        (c (third hf))
        (d (fourth hf)))

    (if (and (same-sign? c (+ c d))
             (let ((limit1 (quotient      a       c))
                   (limit2 (quotient (+ a b) (+ c d))))
               (= limit1 limit2)))
        (let ((term (quotient a c)))
          (let ((new-c (- a (* c term)))
                (new-d (- b (* d term))))
            (values term (list c d new-c new-d))))
        (values #f #f))))
We can combine these two steps and make something useful. For example, we can print the value of applying a homographic function to a continued fraction incrementally, printing the most significant digits before computing further digits.
(define (print-hf-cf hf cf)
  (call-with-values (lambda () (partly-evaluate hf))
    (lambda (term hf*)
      (if (not term)
          (call-with-values (lambda () (partly-apply hf cf))
            print-hf-cf)
          (begin
            (display term) 
            ;; take reciprocal and multiply by 10
            (let ((a (first hf*))
                  (b (second hf*))
                  (c (third hf*))
                  (d (fourth hf*)))
              (print-hf-cf (list (* c 10) (* d 10)
                                 a        b)
                           cf)))))))
But how often are you going to apply a homographic function to a continued fraction? Fortunately, the identity function is homographic (coefficients are 1 0 0 1), so applying it to a continued fraction doesn't change the value. The square root of 2 is a simple continued fraction with coefficients [1 2 2 2 ...] where the 2s repeat forever. We apply the identity homographic function to it and print the results:
(printcf (list 1 0 0 1) sqrt-two)
14142135623730950488016887242096980785696718^G
; Quit!
As you can see, we start printing the square root of two and we don't stop printing digits until the user interrupts.

A fancier version could truncate the output and print a decimal point after the first iteration.

by Joe Marshall (noreply@blogger.com) at September 18, 2014 07:06 PM