Full of stars

Last january, Gna! Hotspot ran a very interesting interview with Étoilé’s main developers (David Chisnall, Jesse Ross, Nicolas Roard, Quentin Mathé and Yen-Ju Chen). These guys are not happy with current desktop environments, and have decided to build their own on top of GNUstep, which is in turn inspired by NeXT/OpenStep, the origin of Mac OS X. In fact, their peeves go far beyond the UI layer, and cover the whole Unix architecture (see, for instance, David’s Ten things I hate about Unix).

Instead of just complaining and telling everybody how his or her environment sucks, they have rolled up their sleeves and produced actual code: the Étoilé project is the umbrella for a series of libraries and frameworks aimed at fulfilling their vision.

The nice thing about Cocoa/GNUstep is that they are probably the only production-ready libraries written in a dynamic language, namely, Objective-C. Although it is not as good as Smalltalk (on which it is inspired) or any Lisp, Objective-C is a far, far better option than the usual C or C++ used by other mainstream toolkits. Of course, one could try to improve instead current support for really nice languages (see my Objective-C related posts), but an interesting way of doing that could be building on top of these projects. As mentioned in the interview, the Étoilé developers are all for dynamic languages, and, if you look carefully at their Making Computers Suck Less presentation, you’ll notice that they’re already planning support for Smalltalk or Ruby. Their proposed architecture is also interesting in other ways reminiscent of dynamic environments like Smalltalk’s or prototype based systems, including the everything (as in up to the user level) is a manipulable object idea, or orthogonal persistence.

The later release includes, among others, the following goodies:

  • Camaelon is a theme engine that goes a long way into disproving the GNUstep default ugliness.
  • LuceneKit is a class-to-class port of Lucene (a high-performance, full-featured text search engine library in Java) in GNUstep.
  • OgreKit is a port of the Cocoa regular expression engine of the same name.
  • SQLiteClient is a SQLClient/SQLite port from SQLClient library in GNUstep/devl-libs. It uses sqlite3 library and is supposed to work only on Mac OS X for portability of Etoile.
  • UnitKit is a unit test framework for Objective-C, again based on a Cocoa project.

All in all, a pretty interesting project. And, if you like reading about your fellow programmers toilings, don’t miss the Étoilé blog, where their developers give details about their daily efforts.

Tags: , , ,

More on exotic input methods

Not surprisingly, the multi-touch interface i mentioned a few days ago has also caught the attention of some of the folks at the Squeak-devel list. After all, Squeak and Smalltalk worlds are about the only programming environments trying to go beyond the typical file-based coding style. Of course, there’s much to say in favour of ASCII files as the primary code substratum, as well as against. I’m not entering in a profound debate on these issues in this post. Instead, i will share a few pointers to systems and research that try to go beyond traditional input methods and that i find amusing, and let you decide on their relevance.

Kitty glovesFirst, some pointers from the above mentioned Squeak-devel thread. Besides a link to the Multi-Touch Interaction Research site (which gives some more information on the guys behind the fancy video), Kitty Tech (non-flash entry here) has been mentioned a couple of times. As explained in the site, the Kitty project provides a futuristic glove letting you typing without a keyboard: just join a couple of contacts (by joining the thumb and any other finger) to produce a give character. Touch typing The image on the right shows how it works. Besides fun, this looks like a good keyboard replacement for portable devices, but other than that, i don’t see it as a revolution in the way we program. That said, it may help as a complement to things like multi-touch interfaces for my dreamed Self-like environment. The TactaPad would probably be more interesting for such an environment: it’s a system that shows an overly of your hands (which move on a tactile pad) on the screen, and lets you manipulate objects in there and actually feel them. The application to drawing programs is obvious, and hence to my pet prototype-based system. Another nice thing about TactaPad is that it is also a multi-touch system: you can use simultaneously all your fingers to manipulate objects, going far beyond the functionality a mouse provides. Take a look at these videos, they’re really amusing. Add a split keyboard or a couple of Kitty gloves and there you go.

Of course, applying these innovative technologies to programming depends on developing more visual, less text-based languages and environments; and the question of whether such environments can be as powerful and convenient as the traditional ones is controversial, to say the least. Before discovering Squeak and, specially, Self, i would have probably joined the skeptical, conservative side. Now i’m not so sure.

Needless to say, you’re are not limited to your fingers when it comes to alternative input technologies. Voice recognition systems have a long history, as shown in this excellent collection of videos (some of them from the seventies!) from MIT’s Speech Interfaces Group. Somehow, voice input has not caught up, neither to general use nor to programming environments. I still think they can be useful, though. An interesting project in this area is DivaScheme, which enhances DrScheme with voice-based program editing. It works by, first, defining a series of commands for structured Scheme code editing, and then, providing voice access to those commands. (Unfortunately, DivaScheme works out of the box only with an expensive and Windows-based speech recognition system, and i’ll have to spend an afternoon configuring the free Sphinx system to try it out.) Not as fancy as the previous stuff, but maybe more useful. Let me say in pass that the idea of defining a set of editing commands that are s-expression based instead of character-based is an obvious step that should be taken by any decent editor (and, of course, used by any decent programmer). Emacs lispers, for instance, should never leave home without Taylor Campbell’s paredit (or reading Marco’s highly opinionated guide on Lisp editing).

Tags: , , , , ,

Driving iTunes with Scheme, with a fold tutorial and a Haskell book

In this pretty detailed tutorial, Jim Ursetto puts his Cocoa/Chicken bridge to work. Jim noticed that some of his music files were forgotten by iTunes, and wanted to reimport them without losing any metadata. His article

documents my attempt to do just that by building an application in Chicken Scheme, using the bindings to Objective-C and Cocoa provided by the objc egg. It’s targeted at the intermediate Scheme programmer, who may have some experience with Cocoa. It may also be useful to a beginner looking for examples of an interactive development process, and to a non-Scheme user for the same reason.

Jim has taken the time to document also the program’s design and coding processes, so you’ll not only learn about Cocoa or how to use the Scheme bridge, but also about property lists parsing, symlink creation or exception handling. In addtion, you will have the chance of looking over a fellow programmer shoulder having fun for a while.

Programming in HaskellIt’s a long read, but a very good one. And just in case you don’t get to the end, don’t miss Jim’s last recommended reading: a tutorial on the expressiveness and universality of fold, by Graham Hutton. Graham, by the way, happens to be a Haskell and functional programming erudite and professor, so you may be interested in his publications, including the forthcoming book Programming in Haskell, whose first five chapters are available in PDF here.

Tags: , , , , ,

Contracts, Felleisen and Elements of Style

I’ve found a very interesting Guide to PLT Scheme Contracts in a temp directory of Matthias Felleisen’s site. It’s a very recent “incomplete draft”, but it’s already a nice reading for all of you PLTers interested in the nice Design by Contract extensions found among the many goodies included with PLT Scheme.

Matthias’ site, by the way, is full of very interesting stuff, including the quotations in its front page or the awesome list of publications.

I also found, browsing around his site, an unexpected jewel: a link to Strunk and White’s Elements of Style, which points to the book’s full, searchable text. Before you ask what this has to do with programming, let me leap onto a giant’s shoulders:

Besides a mathematical inclination, an exceptionally good mastery of one’s native tongue is the most vital asset of a competent programmer.

Edsger Dijkstra, How do we tell truhts that might hurt?

Tags: , ,

Conduits to better Common Lisp packages

Common Lisp’s package system provides a simple way to avoid name clashes by means of separate namespace. No more, no less. Albeit having their shadowy corners, as illustrated in this excellent tutorial by E. Gat, packages are very easy to use and, most of the time, get the work done. Basically, think of a package as a map from strings to symbols, with associated lookup functions, and bindings resolved at read time.

But, simple as they are, packages in CL are second-class citizens: you cannot modify them at runtime, add new symbols, create new packages and pass them around as first-class values. For instance, Python modules are dictionary objects (and, as such directly manipulable as, say message receivers or function arguments). Languages in the ML family provide powerful module manipulation facilities, including functors, that is, parametric modules that take modules as arguments and generate new ones (see, for instance, a sample in Alice ML). This kind of trick is not limited to ML: PLT’s units offer the same functionality for Scheme (although i find them cumbersome).

Back to CL, i recently discovered Tim Bradshaw’s Conduits, a nice library adding very interesting functionality to the vanilla package system. For instance, you can define variants of pre-existing modules, or extend a given package including only a subset of the symbols defined by its parent. You can also clone existing packages. Tim’s hacks also include a hierarchical package system for CMUCL that mimics Allegro CL’s one.

Tim’s pages on Lisp and its obscurities are also worth a visit.

Tags: ,

Multi-touch programming?

I was seeing these multi-touch interaction experiments and couldn’t resist: just take a prototype-based development environment like Self‘s and put it inside one of those multi-touch-enabled displays. I think i would love such a programming environment. At least, it would be something different. Programming with Self is a bit like drawing with a good diagram editor: i take a figure, duplicate it, and modify the copy as needed; that’s quite close to the way one programs in Self, and it’s definitely a refreshing way to program. Now, i think most of you will agree that the multi-touch tricks in the video above have direct application to graphical editors, right?

No matter how silly you think this idea of mine is, don’t miss the video: it’s real fun.

Tags:

The Lisp Dictionary

William Bland announced yesterday The Lisp Dictionary, a Lisp-centric document searching facility where he has indexed the Common Lisp HyperSpec, PCL, Successful Lisp, and SBCL‘s documentation strings, plus example code taken from PAIP and PCL. All mixed together in a simple and elegant interface.

(As an aside, William is the author of a very fun Linux module, Schemix, which embeds a Scheme interpreter right into the kernel, although this days he recommends Movitz, a Common Lisp x86 development platform directly “on the metal”.)

If you’re an Emacs user, here’s an elisp function (courtesy of a c.l.l poster named Nick), to search the Lisp Dictionary without leaving your editor:

(defun lispdoc ()
  "searches lispdoc.com for SYMBOL, which is by default the symbol
currently under the curser"
  (interactive)
  (let* ((word-at-point (word-at-point))
	 (symbol-at-point (symbol-at-point))
	 (default (symbol-name symbol-at-point))
	 (inp (read-from-minibuffer
	       (if (or word-at-point symbol-at-point)
		   (concat "Symbol (default " default "): ")
		   "Symbol (no default): "))))
    (if (and (string= inp "")
             (not word-at-point)
             (not symbol-at-point))
	     (message "you didn't enter a symbol!")
	 (let ((search-type
            (read-from-minibuffer
			  "full-text (f) or basic (b) search (default b)? ")))
	  (browse-url (concat "http://lispdoc.com?q="
			      (if (string= inp "")
				  default
				  inp)
			      "&search="
			      (if (string-equal search-type "f")
				  "full+text+search"
				  "basic+search")))))))

Tags: , , ,

Continuation kata

If you have a little Scheme under your belt, just plunge into the challenge right now:

We want to find three integers, x y and z such that both are in the range [2,9] and that they are the lengths of the sides of a right triangle (x^2 = y^2 + z^2). The challenge is to write two procedures, in-range and fail such that the solution to the problem looks like this:

(let ((x (in-range 2 9))
      (y (in-range 2 9))
      (z (in-range 2 9)))
  (if (= (* x x) (+ (* y y) (* z z)))
      (list x y z)
      (fail "no solution")))

In other words, we are after an elegant way of implementing search backtracking: the possible values of the (x, y, z) triplets must be checked in turn, until a solution is found or we exhaust the search space. This is the kind of problem that declarative languages like Prolog solve in a breeze. Scheme does not fare bad, either: the right solution is just a screenful long. Keep on reading if you feel like getting some hints.

I’ve stolen this little exercise from an excellent talk by Marc Feeley on writing a Scheme to C compiler. The example pops up when Marc is discussing what makes such a compiler tricky (that is, what Scheme features are missing in C): tail calls, garbage collection, closures and first class continuations. So here goes the first hint: the solution uses call/cc.

Continuations 101

I couldn’t put a finger on it, but there’s something pesky about continuations: in my experience, they’re hard to grasp at first. And yet, the concept is quite simple: whenever you are evaluating an expression E, there’s someone waiting to do something with the value of E; for instance, in the process of evaluating:

(+ 3 (* 5 4))

if you take E to be (* 5 4), the interpreter is waiting for your result to add 3… this thing to be done to the result of evaluating a (sub)expression can be, quite naturally, represented by a procedure that takes a single argument; in our example, this procedure could be:

(lambda (v) (+ 3 v))

or, if you are evaluating the whole thing on a REPL toplevel that will print the result, maybe something roughly equivalent to:

(lambda (v) (print (+ 3 v)))

It is this (usually invisible) procedure what we call the current continuation. Every expression has a continuation, but in many languages it is only implicit. Scheme gives you the possibility of accessing it. If you write:

(+ 3 (call/cc (lambda (cont) (* 5 4))))

that could be translated as

(+ 3
   (let ((cont (lambda (v) (+ 3 v)))
      (* 5 4)))

Of course, things get only interesting when you use cont; for instance, it is hopefully clear that

(+ 3 (call/cc (lambda (cont) (* 5 4) (cont 18))))

evaluates to 21. Besides writing silly examples and bore your readers to tears, you can put this stuff to good use in a variety of ways. The most immediate is to early scape from a long computation. This procedure multiplies all the elements in a given list:

(define (mult lon)
  (cond ((null? lon) 1)
        ((zero? (car lon)) 0)
        (else (* (car lon) (mult (cdr lon))))))

but it will do a lot of useless work when lon contains a 0. First class continuations allow a better way:

(define (mult-k lon cont)
  (cond ((null? lon) 1)
        ((zero? (car lon)) (cont 0))
        (else (* (car lon) (mult-k (cdr lon) cont)))))

(define (mult lon) (call/cc (lambda (cont) (mult-k lon cont))))

If you understand why this is better than the previous version, you’re on your way to understanding continuations as non-local exits. And if by now you’re thinking that continuations are not, after all, a big deal, quick tell me what

(((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!")

evaluates to, and why. By the way, this nice micro-kata is from TSPL’s section on continuations, which provides a nice, if brief, introduction to call/cc, including a description of another typical use case: the implementation of threading via coroutines. A more extended (but still not too long) discussion of the very same issues can be found in Dann Friedman’s beautiful paper Applications of Continuations.

Finally, if you have a little time in your hands, read through this interesting ll1 mail thread, where guys like Mathias Felleisen, Avi Bryant or Paul Graham have their say on continuations and their uses.

Backtracking

Since coroutines are not needed to solve our original kata, let me gloss over them and jump to the next typical use of continuations: backtracking. A key thing to remember about call/cc is that the continuation passed to the lambda form is a first class value. Among other things, that means that you can store it and use it in a totally unrelated context. Or, in other words, Scheme introduces time-travel in your toolset, with its associated wonders (as in Schelog, a Prolog implemented in Scheme) and headaches.

Let’s see how backtracking can be implemented with the aid of persistent continuations using an example adapted from Jacques Chazarain’s book Programmer avec Scheme (which, by the way, makes for an excellent second book on Scheme, provided you read French). Writing a procedure that looks for the first occurrence of an element in a list that satisfies a given predicate is a piece of cake:

(define (search lst p?)
  (cond ((null? lst) #f)
        ((pair? lst) (or (search (car lst) p?)
                         (search (cdr lst) p?)))
        ((p? lst) lst)
        (else #f)))

where we accept list of lists too. But what if i want to get all findings one by one? I’d like to have a solution generator that returns a procedure returning, in successive calls, each of the occurrences of a solution in the given list. That is, we want to be able to write code like this one:

(define solutions
  (search-generator '(0 ((1 a) 2) b (b c) (((6)))) number?)
(solutions) => 0
(solutions) => 1
(solutions) => 2
(solutions) => 6
(solutions) => 'done

Persistent continuations allow a very clean implementation of search-generator. The strategy is to start the search, and each time we find an element in the list satisfying the predicate store the current continuation (which will keep on searching for more solutions) for later invocations. We then return a procedure that calls the continuation and stores a new one which will resume the search with the rest of the list. You can have a little fun trying to find the solution before reading it below. Or, if you get stuck, to read Ferguson and Duego’s excellent Call with Current Continuation Patterns, where you’ll find examples of call/cc in action.
Got your answer? Well, let’s compare:

(define (search-generator lst p?)
  (let ((success '?)) ;; placeholder for the current continuation
    (letrec ((cont-success ;; next continuation
              (lambda (x) (search lst)))
             (search
              (lambda (elem)
                (cond ((null? elem) 'done)
                      ((pair? elem) (search (car elem))
                                    (search (cdr elem)))
                      ((p? elem) (call/cc
                               (lambda (k) ;; next search will continue from here
                                 (set! cont-success k)
                                 (success elem))))
                      (else 'done)))))
      (lambda () (call/cc (lambda (k)
                       (set! success k)
                       (cont-success 'done)))))))

Once you grasp how this works, you have all the ingredients to solve our original kata.

Not only Scheme

There are other languages with support for first class continuations, SML/NJ and Ruby being the most salient cases. Besides, Seaside implements them for our beloved Smalltalk.

You don’t need call/cc to play some of the tricks discussed above. For instance, one can implement backtracking in Python (the linked article contains also an intro to continuations) or Standard SML (ditto, also with examples in Pascal, and, of course, SML), using a technique known as Continuation Passing Style, or CPS, that consist on passing explicitly the continuation to each of your functions. Explaining CPS would take another article, so, for now, i will let you explore it by yourself, but i’ll mention that armed with CPS you can, essentially, play all the call/cc tricks. A few years ago, type theorist extraordinaire Benjamin C. Pierce asked in the Caml mailing list about cool CPS usages, and took the time to summarize the responses he got. It contains pointers to many mind-bending readings.

The solution

I almost forgot: if you give up finding our kata’s solution or want to check it out, you’ll find it in Marc Feeley’s talk for the Montreal Scheme/Lisp Users Group. As i’ve mentioned, it deals with the implementation of a Scheme to C compiler (Marc is the lead developer of Gambit-C), which is based on CPS. The site contains links to the talk slides and videos, and a beautiful pure-scheme implementation of the compiler. Enjoy.

Tags: , , , ,

On Lisp On Line and new PLAI

I’m sure i don’t need to comment or recommend Paul Graham’s On Lisp. Nor tell you that it’s available from the author’s site in PDF format. However, you may be (as i was) unaware that there’s an on line HTML version, complete with a search box and settable CSS. I also routinely install it in texinfo format, for easy reference inside Emacs.

On a related note, i’ve also recently updated my copy of Shriram Krishnamurthi‘s Programming Languages: Application and Interpretation, a wonderful book that Shriram uses in his Programming Languages course at Brown University. It covers almost every single interesting corner of PL-land, including interpreters, laziness, recursion, continuations, garbage collectors, type theory, declarative programming or macros. The book commences with an invitation:

I think the material in these pages is some of the most beautiful in all of human knowledge, and I hope any poverty of presentation here doesn’t detract from it. Enjoy!

Needless to say, poverty of presentation is hardly to be seen in this excellent work.

Happy reading.

Tags: , , , , , ,

Scheme code kata

A list manipulation mini-challenge for those of you learning Scheme (or any other Lisp), posted by Jens Axel Søgaard in c.l.s:

Consider the problem of turning a list consisting
of a mix between symbols and non-symbols into a
list of lists of the symbol and its following
non-symbols. That is:

Input:    ({ *} ... )
Output:   (( (*)) ...)
Example:     (a 1 2 3 b 4 5 c d 8 9 e)
           -> ((a (1 2 3)) (b (4 5)) (c ()) (d (8 9)) (e ()))

It is possible to do this in a variety of ways, but
I’d like to see an easy-to-read yet short solution.

There are some elegant solutions in the corresponding c.l.s news thread, but it will be a lot funnier if you try your hand at it first. Extra kudos for those of you posting your solution in the comments section :).

Tags:

Posted in Scheme. 9 Comments »
Follow

Get every new post delivered to your Inbox.

Join 26 other followers