Developing iPhone Apps in Scheme

Over at jlongster, James Long has a series of posts on developing iPhone applications using Gambit Scheme (the posts are collected here). It's still a work in progress, but James has a couple of working examples, some FFIs to get at iPhone functionality such as touch and the accelerometer, and even a screencast on how to set up a remote debugger.

This is great work and a nice chance to try out some iPhone development without having to delve into Objective-C. The posts include step-by-step directions for setting up the environment and the source for the examples is available for viewing or download. There is also a git repository available at github.

Emacs 23 Released

The long awaited Emacs 23.1 was released yesterday as promised. I've been running the development version on a Mac for some time without any real problems, so there's no reason not to upgrade and give it a try.

In Search of a Problem

I don't know what to make of this. What, exactly, is the market for vim with Emacs key bindings? Vim users envious of Emacs Pinky? In the About Vimacs page, the author explains that we was an Emacs user frustrated by the lack of speed in Emacs and the necessity to learn Lisp to perform customization. I have to say I'm not convinced. For sure it's a clever hack and does indeed scratch the itch that the author had but, really, it seems to me to be a solution in search of a problem.

Update: Fixed a typo.

Implementing Continuations

Over at Lambda the Utimate they're featuring the classic paper Representing Control in the Presence of First-Class Continuations by Dybvig and Bruggeman. I remember reading this paper years ago at a time when I was still wrestling with the notion of continuations and how they worked. While reading the paper, everything suddenly snapped into place and it all made sense. If you're a Scheme programmer and you haven't read this paper yet, you should. You'll be glad you did.

Nekthuth

Frank Duncan has been working on Nekthuth, a solution to the problem of programming in Lisp using the vim editor that I complained about previously. So far Nekthuth only works with SBCL and it lacks most of the features in SLIME, but it is a start.

Of course, we've heard the promise of a solution before only to be disappointed, so I'm still glad I went through the pain of switching to Emacs. Unfortunately, the architecture of vim makes it difficult to build a SLIME-like solution, so Frank's achievement is all the more striking. If you absolutely, positively can't give up vim but need to program in Lisp, you should give it a try.

Continuations in Scheme

Here's a nice elementary explanation of continuations from Vijay Matthew over at (λ x.xx) (λ x.xx)

Stop Iterating Down Lists

Over at Abstract Heresies Joe Marshall has two posts that make the point that we shouldn't write code to iterate down a list. We should, instead, use higher order functions such as map or fold. Thus, if we want to sum the squares of a list of numbers, we shouldn't explicitly iterate down the list like this

(define sum-of-squares
 (lambda (numbers)
   (let sum ((l numbers) (sos 0))
     (if (null? l)
         sos
         (sum (cdr l) (+ sos (* (car l) (car l))))))))

but should write something like

(define sum-squares
 (lambda (numbers)
   (fold (lambda (num sum) (+ sum (* num num)))
         0
         numbers)))

It's a good point and one that we tend to forget no matter how fervently we worship at the Church of SICP.

Speaking of the Fibonacci Sequence

Over at Programming Praxis, a recent problem involved the continued fraction

We can write this as the recursion relation

G₀ = 1

G_n+1 = 1 + 1/G_n

The problem is to find G₂₀₀. It's not hard to see that the G_n converge to some number G and therefore that G = 1 + 1/G, and so G is the golden ratio.

More interesting, though, is that G_n = Fib_n+1/Fib_n, where Fib_n is the n^th Fibonacci number starting from 1—that is, the Fibonacci sequence 1, 1, 2, 3, 5, … . Exercise 1.19 of SICP develops a fast method of calculating Fib_n+1 and Fib_n at the same time in O(log n) time (it's very much like the fast exponential routines). This gives us an elegant and fast solution to the problem

(define golden-ratio
(lambda (n)
(let iter ((n n) (p 0) (q 1) (a 1) (b 1))
  (cond ((= n 0) (/ a b))
        ((even? n) (iter (/ n 2) (+ (* p p) (* q q))
                         (+ (* 2 p q) (* q q)) a b))
        (else (iter (- n 1) p q (+ (* b q) (* a q) (* a p))
                    (+ (* b p) (* a q))))))))

I like this problem because it's a chance to use the fast Fibonacci

calculator from SICP, an opportunity that doesn't come up often.

Fibonacci Numbers as a Dynamic Programming Problem

Early in our education as Lisp programmers we all learn the naturalness and power of recursion. We also learn that it can sometimes be the spectacularly wrong way of doing things. The canonical example is implementing the Fibonacci function

recursively.

(defun fib (n)
(if (<= n 1)
    n
    (+ (fib (- n 1)) (fib (- n 2)))))

This is a bad implementation because it repeatedly calculates the F(n) resulting in an exponential running time and an O(n) space requirement. But if we (slightly) rewrite the definition as a recurrence relation

F₀ = 0 F₁ = 1 F_n = F_n-1 + F_n-2 we notice that we have the makings for a classical Dynamic Programming solution: a recursion relation that specifies the solution of the problem in terms of one or more subproblems. It's straightforward to implement this solution

(defun fib-dp (n)
(let ((F (make-array (max 2 (1+ n)))))
  (setf (aref F 0) 0)
  (setf (aref F 1) 1)
  (do
   ((i 2 (1+ i)))
   ((> i n) (aref F n))
    (setf (aref F i) (+ (aref F (- i 1)) (aref F (- i 2)))))))

Here the amount of space and the amount of work are both O(n). We can make a further optimization if we notice that we don't need to store all the values of F, just the last two. This gives us a solution that is O(n) in time and O(1) in space.

(defun fib-opt (n)
(if (<= n 1)
    n
    (let ((F-last 1) (F-second-last 0) temp)
      (do
       ((i 2 (1+ i)))
       ((> i n) F-last)
        (setf temp F-last
              F-last (+ F-last F-second-last)
              F-second-last temp)))))

Finally, we can come full circle and reintroduce recursion. Because this is tail recursion the solution still uses constant space—at least for those Lisps (i.e. pretty much all modern Lisps) that optimize tail recursion.

(defun fib-opt2 (n)
(if (<= n 1)
    n
    (labels ((fib (n F-last F-second-last)
               (if (zerop n)
                   F-last
                   (fib (1- n) (+ F-last F-second-last) F-last))))
      (fib (1- n)  1 0))))

None of this is earth shattering, of course, but it's a nice illustration of how shifting your viewpoint a little can help you arrive at what SICP describes as a non-straightforward solution.

Dragged kicking and screaming to Emacs (2)

At the end of my last post, I was happily going about my business secure in the knowledge that I was a lifetime vim user. Then I stumbled across Paul Graham's essay, Revenge of the Nerds. This essay—like many of his early ones—was about the power and superiority of Lisp. Unlike many programmers of my generation, I had remained mired first in assembly language and then C and had never learned Lisp, but Paul's essay inspired me to finally give it a try. So I picked up a copy of Paul's ANSI Common Lisp, read it cover to cover, and was hooked.

I quickly moved to Scheme and spent the next three or four years using it almost exclusively. I read Peter Seibel's Practical Common Lisp, and started spending more time with CL. Eventually, I divided my time pretty evenly between CL and Scheme.

One Small Problem

Although I was having great fun playing with the DNA of the universe (XKCD notwithstanding), there was one small problem: it's really hard to program in Lisp effectively using vim. Yes, you can have vim running in one window and the REPL in another, save your edits, load them from the REPL and run your tests, but that's not really a smooth work flow. Yes, some Lisps and Schemes have an IDE, but using them means you have to juggle multiple editors and that you'll probably never master any of them. And yes, I know all about all the vim SLIME-like add ons that are coming real soon now, but after a while one tires of waiting.

So once again I downloaded the latest emacs sources, compiled and installed them, ran through as much of the tutorial as I could stand, loaded Quack and SLIME and started life as a born-again Emacs user. And it was painful. Oh my it was painful. All that vi muscle memory mated with the Emacs key sequences to produce such mutant offspring as CTL-k to scroll backwards—this was especially hilarious because I would often type CTL-k several times before I realized I was deleting lines rather than moving up.

There were other, more subtle, hurdles too. Vi users tend to fire up the editor when they need to edit a file and close it immediately afterwards. Emacs users tend to leave the editor open all the time and even keep buffers around weeks after they're finished with them. So on top of retraining my muscle memory I also had to learn a new way of working.

Epilog

I've been using Emacs full time for about a year now, and am currently running the excellent Emacs 23. All in all, it's been worth the struggle. Writing Lisp code is so much easier that that one thing alone was worth the price of admission. I really like that I can add functionality that exactly suits my needs simply by writing some Lisp. Like many Emacs users, I discovered that the .emacs file is a splendid time trap, easily soaking up any cycles that wander within its event horizon.

I even use some of those features that I made fun of as a vim user. For example, Org-mode and remember are part of my work flow now and I don't know how I ever got along without them. I still don't play Towers of Hanoi though.

Dragged kicking and screaming to Emacs (1)

I've been a staunch vi user for more than a quarter of a century, and although I never enlisted in the vi/Emacs holy wars, I was firm in my belief that vi—and especially its vim incarnation—was the right thing. I liked that it was lightweight and would start in an instant (although to be fair, that was less true of vim). I considered vi's modality—the main complaint of its detractors—a feature because it meant I didn't have to take my hands off the home row. It was fast and after all those years I was fast when I used it: all those cursor movement commands were burned into my muscle memory and I didn't have to think about them. It was almost as if vi were reading my mind.

Emacs, on the other hand, seemed bloated and clunky. Its huge memory footprint (neatly captured by the retronym Eventually Mallocs All of Core Storage) meant that it was painfully slow to start up. Its lack of modality meant that control sequences had to make extensive use of the metakeys giving rise to another retronym: Escape-Meta-Alt-Control-Shift. Its list of features, including a Towers of Hanoi puzzle seemed almost a caricature of marketing-driven featuritis.

Still, there were some things in Emacs that did invoke envy in the vi user. Its use of multiple windows meant that a user could edit related files (or different views of a single file) at the same time. Multiple buffers meant that a user could quickly switch between files without having to save the current file. Dired meant that a user could see the files in a directory and pick the right one to edit without having to fire up a separate shell and run ls. The built-in man command meant the user didn't have to leave the editor to make a quick check on the exact calling sequence of a function.

So every few years I'd make an attempt to adopt Emacs, but I was always overcome by minor annoyances: the jump scrolling seemed jarring; cursor control was physically painful; moving forward or backwards by words left the cursor in unexpected places; even the terminology seemed wrong (for example, yank means something else to the vi user). The result was always the same. I'd come home to vi but wish it had some of those neat Emacs features.

Finally, vim came along and provided most of the missing pieces that Emacs had but vi didn't. I was now completely content with vim and fully expected to stay with it until the heat death of the universe. But then something happened that changed everything.

—to be continued

A Surprising Solution

In Exercise 1.3 of SICP, we are asked to define a procedure that take three numbers as input and returns the sum of the squares of the 2 larger numbers. We already have a procedure, sum-of-squares, that returns the sum of the squares of its two inputs, so a natural solution is something of the sort

(define sum-of-squares-of-max
  (lambda (a b c)
  (sum-of-squares
  (if (< a b) b a)
  (if (< (if (< a b) a b) c) c (if (< a b) a b)))))

or, perhaps, the less opaque

(define sum-of-squares-max
  (lambda (a b c)
  (cond ((and (<= a b) (<= a c)) (sum-of-squares b c)) ;;a smallest
          ((and (<= b a) (<= b c)) (sum-of-squares a c));;b smallest
          (else (sum-of-squares a b)))))                ;;c smallest

Joe Marshall over at Abstract Heresies offers this surprising and elegant solution

(define sum-of-squares-max
  (lambda (a b c)
  (if (and (<= a b) (<= a c))                         ;;a smallest
        (sum-of-squares b c)
      (sum-of-squares-max b c a))))

Welcome to Irreal

This is a blog primarily about Scheme and Lisp and their world of

infinite fun. As part of exploring that world, I'll also consider

related subjects such as Emacs, Slime, Org-Mode and, really, anything

else that excites my geek sensibilities.

The idea for Irreal came about when I stumbled upon a series of

posts on Eli Benersky's Website in which he presented his solutions to

the problems in Structure and Interpretation of Computer Programs

(SICP). I have long considered SICP to be one of the best books on

the art and craft of computer programming ever written. Because it

had been some time since I'd read SICP and I'd never worked through

all the problems, I decided that I would reread the book and write up

solutions to the problems in a form suitable for a solution manual—I

was aiming at the level of detail in the solutions to the exercises in

Knuth's Art of Computer Programming. One of the main purposes of

this blog, at least initially, is to record observations about the

exercises, their solutions, and any other technical issue that comes

up along the way.