Using OpenGL with Arc

I saw a posting on news.ycombinator entitled "Take the Tetris test (an Arc version, anyone?)", which suggested writing a simple Tetris-like game. One obvious problem with doing this in Arc is the lack of graphics support. But how hard could it be to use OpenGL graphics from Arc?

It turns out that using OpenGL from Arc is harder than I expected, but possible, given enough hacking on Arc's underlying Scheme implementation. In this article, I discuss how I got OpenGL to work.

Challenge 1: How to access libraries from Arc

The first challenge is that the official Arc release does not let you access Scheme libraries or functions. Not at all. Even though Arc is implemented on top of MzScheme, there is no mechanism to access the underlying MzScheme implementation. If you want to access Scheme, you must actually modify the Arc language implementation by hacking on the Scheme code that implements Arc.

The unofficial Anarki implementation is a modified version of Arc that provides access to Scheme (as well as many other useful improvements). However, I decided to base my OpenGL project on the offical Arc implementation rather than Anarki.

I replaced the Arc implementation file ac.scm with a modified version called arc-gl.scm that gives me access to the necessary Scheme functions. The relevant Scheme code is:

(require (lib "mred.ss" "mred")
       (lib "class.ss")
       (lib "math.ss")
       (prefix gl- (lib "sgl.ss" "sgl"))
       (lib "gl-vectors.ss" "sgl"))

; List of functions to export from Scheme to Arc
(map (lambda (s) (xdef s (eval s)))
   '(gl-shade-model gl-normal gl-begin gl-end gl-vertex gl-clear-color gl-clear
     gl-push-matrix gl-pop-matrix gl-rotate gl-translate gl-call-list gl-flush
     gl-light-v gl-enable gl-new-list gl-gen-lists gl-material-v gl-viewport
     gl-matrix-mode gl-load-identity gl-frustum gl-light-v gl-enable gl-end-list
     gl-scale sin cos))

; Arc doesn't provide access to vector, so make gl-float-vector
; take individual arguments instead of a vector
(xdef 'gl-float-vector (lambda (a b c d) (vector->gl-float-vector (vector a b c d))))

First, the code imports the necessary libraries. Next, it uses xdef to allow access to the list of specified Scheme functions. I included the OpenGL functions I used; you will need to extend this list if you want additional OpenGL functionality. I also include sin and cos; they are missing from Arc, which is almost pervesely inconvenient.

To get my code:

• Download arc-gl.zip.

This contains arc-gl.scm, the updated Scheme code; arch.arc, the arch demo in Arc; and gears.arc, the gears demo in Arc. It is also available from the Anarki git.

Challenge 2: Where is OpenGL?

OpenGL isn't part of the plain vanilla MzScheme that is recommended for Arc, but it is part of DrScheme. Both DrScheme and MzScheme are versions of Scheme under the PLT Scheme umbrella; MzScheme is the lightweight version, while DrScheme is the graphical version that includes MrEd graphics toolbox and the OpenGL bindings for Scheme. Thus:

• Download and install DrScheme version 352.

An alternative to OpenGL would be using MrEd's 2-d graphics; I've described before how to add simple graphics to Arc. However, I wanted to use the opportunity to learn more about OpenGL.

Challenge 3: Running an Arc REPL in PLT Scheme

It's straightforward to run as.scm inside PLT Scheme and get an Arc REPL. However, a problem immediately turns up with OpenGL

An OpenGL animation will lock up as soon as the Arc REPL is waiting for input. The problem is that MrEd is built around an event loop, which needs to keep running (similar to the Windows message loop). When the REPL blocks on a read call, the entire system blocks.

The solution is to implement a new GUI-based Arc REPL instead of the read-based REPL. MrEd provides text fields that can be used to provide non-blocking input. When the input is submitted, the event loop executes a callback, which can then run the Arc code. Of course, the Arc code needs to return reasonably promptly, or else things will be locked up again. However, the Arc code can start a new thread if it needs to do a long-running computation.

The following MzScheme code creates a frame, text-field for output, text-field for input, and a submit button, and executes the submitted code through arc-eval. It is analogous to the REPL code in ac.scm. I put this code in arc-gl.scm.

(define frame (instantiate frame% ("Arc REPL")))
(send frame show #t)

(define (cb-submit a b) (on-err (lambda (c)
 (append-tf (exn-message c)))
      (lambda ()
 (append-tf (send in-field get-value))
 (append-tf (format "~a" (ac-denil (arc-eval (read (open-input-string
                                  (send in-field get-value)))))))
 (send in-field set-value ""))))


(define tf (instantiate text-field% ("" frame)
    (style '(multiple)) (min-width 600) (min-height 150) (enabled #f)))

(define (append-tf str)
    (send tf set-value (string-append (send tf get-value) str "\n")))

(define in-field (instantiate text-field% ("" frame) (style '(single)) ))

(define bb  (instantiate button% ("submit" frame) (style '(border)) (callback cb-submit)))

To start up Arc with the new REPL:

• Load the new REPL code into the same directory as the original Arc files.
• Run drscheme.
• Go to Language -> Choose Language -> PLT -> Graphical. Click Ok.
• Go to File -> Open -> arc-gl.scm
• Click Run

As you can see from the screenshot, the REPL doesn't get any points for style, but it gets the job done.

Challenge 4: Using Scheme's object model

The mechanism above can't be used to access PLT Scheme's windowing operations, because they are heavily based on the Scheme object implementation, which is implemented through complex Scheme macros. Thus, I can't simply map the windowing operations into Arc, as I did with sin. If the operations are called directly, they will try to apply Scheme macros to Arc code, which won't work. If they're called after Arc evaluation, the Arc implementation will have already tried to evaluate the Scheme macros as Arc code, which won't work either.

I tried several methods of welding the Scheme objects into Arc, none of which are entirely satisfactory. The first approach was to encapsulate everything in Scheme and provide simple non-object-based methods that can be called from Arc. For example, an Arc function make-window could be implemented by executing the necessary Scheme code. This works for simple operations, and is the approach I used for simple 2-d graphics, but the encapsulation breaks when the code gets more complex, for example with callbacks and method invocations. It is also unsatisfying because most of the interesting code is written in Scheme, not Arc.

Another approach would be to fully implement Scheme's object model in Arc, so everything could be written in Arc. That was way more difficulty and work than I wanted to do, especially since the object system is implemented in very complex Scheme macros.

My next approach was to implement an exec-scheme function that allows chunks of Scheme code to be called directly from inside Arc. This worked, but was pretty hacky.

Minor semantic differences between Arc and Scheme add more ugliness. Arc converts #f to nil, which doesn't work for Scheme code that is expecting #f. I hacked around this by adding a symbol false that gets converted to #f. Another problem is Arc lists get nil added at the end; so the lists must be converted going to and from Scheme.

Finally, I ended up with a somewhat hybrid approach. On top of eval-scheme, I implemented Arc macros to wrap the object operations of send and invoke. These macros try to do Arc compilation on the Arc things, and leave the Scheme things untouched. Even so, it's still kind of an ugly mix of Scheme and Arc with lots of quoting. I found writing these macros surprisingly difficult, mixing evaluated and unevaluated stuff.

As an aside, Scheme's object framework uses send foo bar baz to invoke bar on object foo with argument baz. I.e. foo.bar(baz) in Java. I found it interesting that this semantic difference made me think about object-oriented programming differently: Scheme objects are getting sent a message, doing something with the message, and providing a reply. Of course, this is the same as invoking a method, but it feels more "distant" somehow.

At the end of this, I ended up with a moderately ugly way of creating Scheme objects from Arc, providing callbacks to Arc functions, and implementing instantiate and send in Arc. This isn't a full object implementation, but it was enough to get the job done. For example, to instantiate the MrEd frame% class and assign it to an Arc variable:

(= frame (instantiate 'frame% '("OpenGL Demo" 'false)))

A function to send a refresh message to the canvas:

(def refresh () (send arc-canvas refresh))

Defining a subclass of canvas% to display the image is uglier as it is Arc code that's mostly in Scheme, but using the Arc callbacks:

(eval-scheme `(define arc-canvas%
(class* canvas% ()
  (inherit refresh with-gl-context swap-gl-buffers get-parent)
  (define/public (run) (,ex-run))
  (define/override (on-size width height)
     (with-gl-context (lambda () (,ex-on-size width height))))
  (define/override (on-paint) (with-gl-context ,ex-on-paint))
  (super-instantiate () (style '(gl no-autoclear))))))

Finally doing something with OpenGL in Arc

Here's a simple example of an animated arch displayed in OpenGL. To run this example, download the code and start up DrScheme as described above. Then:

• From the Arc REPL (not the Scheme REPL) execute:

  (load "arch.arc")
  (motion)
  

The code, in arch.arc, has several parts. The arch function does the OpenGL work to create the Arch out of triangles and quadrilaterals. It uses archfan to generate the triangle fan for half of the front of the arch. The full code is too long to include here, but the following code, which generates the inside of the arch, should give a taste:

(for i 0 (+ n n -1)
(withs (angle (* (/ 3.1415926 n 2) i)
  angle2 (* (/ 3.1415926 n 2) (+ i 1)))
  (gl-normal (* r (cos angle)) (* r -1 (sin angle)) 0)
  (gl-vertex (* r -1 (cos angle)) (* r (sin angle)) z)
  (gl-vertex (* r -1 (cos angle)) (* r (sin angle)) negz)
  (gl-normal (* r (cos angle2)) (* r -1 (sin angle2)) 0)
  (gl-vertex (* r -1 (cos angle2)) (* r (sin angle2)) negz)
  (gl-vertex (* r -1 (cos angle2)) (* r (sin angle2)) z)))

The next section of the code contains the graphics callback functions:

• ex-run: the animation entry point called by the timer. Updates the rotation and refreshes the image.
• ex-on-paint: uses OpenGL commands to draw the arch
• ex-on-size: handles window resize and initial size. The OpenGL model (arch, lighting, projection) is set up here.

The last part of the code calls into Scheme to create the canvas and tie it to the appropriate callbacks, create the frame holding the canvas, and display the frame.

I find the arch-generation code somewhat unsatisfying stylistically, as there is a lot of duplicated code to generate the vertices and normal vectors for the front, back, and sides. I couldn't come up with a nice way to fold everything together. I suppose the Arc-y solution would be to write a DSL to express graphical objects, but that's beyond the scope of this project.

Let me mention that low-level OpenGL is not particuarly friendly for exploratory programming. It's tricky to generate complex shapes correctly: it's really easy to end up with the wrong normals, vertices that aren't clockwise, non-convex polygons, and many other random problems. I find it works much better to sketch out what I'm doing on paper first; if I just start coding, I end up with a mess of bad polygons. In addition, I've found that doing the wrong thing in OpenGL will lock up DrScheme and/or crash my machine if I'm unlucky.

The gears example

I also ported the classic OpenGL "gears" demo from Scheme to Arc. This demo includes GUI buttons to rotate the gears. (The animated GIF at the top of the page shows the program in operation.) This is a fairly straightforward port of gears.scm that comes with DrScheme. To run it:

• Enter into the Arc REPL: (load "gears.arc")

The interesting thing to note in gear.arc is the horizontal-panel%, vertical-panel%, and button% objects that provide the UI controls. They are linked to Arc functions to update the viewing parameters. For example, in the following, note that instantiate is passing Arc code (using fn) to the Scheme constructor for button%. The tricky part is making sure the right things get evaluated in the right language:

 (instantiate 'button% (list "Right" h (fn x (ex-move-right)))
                       '(stretchable-width #t))

How did I generate the animated gifs? Just brute force: I took some screenshots and joined them into an animated gif using gimp. The real animation is smoother. I found the animated gifs are a bit annoying, so I added JavaScript to start and stop them. The animation is stopped by substituting a static gif.

Conclusion

So what about the Tetris challenge that inspired my work on OpenGL? After all the effort to get OpenGL to work in Arc, I lost momentum on the original project of implementing the game. (This is an example of why Arc is bad for exploratory programming. If I wanted to get something done, I would have been much better off using DrScheme directly.) Maybe I'll complete the game for a future posting.

Why Arc is bad for exploratory programming

Recently, I've been reading Programming Collective Intelligence, which is a practical guide to machine learning algorithms, showing how to build a recommendation system, implement a search engine, classify documents, mine websites, use genetic algorithms and simulated annealing, and implement other machine learning tasks. The book shows how to implement each of these in surprisingly few lines of Python.

The book is an excellent example of exploratory programming, showing how to incrementally build up these applications and experiment with different algorithms from the Python interactive prompt. For instance, topic clustering is illustrated by first implementing code to fetch blog pages from RSS feeds, breaking the pages into words, applying first a hierarchical clustering algorithm and then a K-means clustering algorithm to the contents, and then graphically displaying a dendrogram showing related blogs. At each step, the book shows how to try out the code and perform different experiments from the interactive prompt.

By using Python libraries, each step of implementation is pretty easy; the book can focus on the core algorithms, and leave the routine stuff to libraries: urllib2 to fetch web pages, Universal Feed Parser to access RSS feeds, Beautiful Soup to parse HTML, Python Imaging Library to generate images, pydelicious to access links on del.icio.us, and so forth.

If you want more details than the book provides (it is surprisingly lacking in references), I recommend Andrew Moore's online Statistical Data Mining Tutorials, which covers many of the same topics.

What does this have to do with Arc?

While reading this book, I was struck by the contradiction that this book is a perfect example of exploratory programming, Arc is "tuned for exploratory programming", and yet using Arc to work through the Collective Intelligence algorithms in Arc is an exercise in frustration.

The problem, of course, is that Arc lacks libraries. Arc lacks basic functionality such as fetching a web page, parsing an XML document, or accessing a database. Arc lacks utility libraries to parse HTML pages or perform numerical analysis. Arc lacks specialized API libraries to access sites such as del.icio.us or Akismet. Arc lacks specialized numerical libraries such as a support-vector machine implementation. (In fact, Arc doesn't even have all the functionality of TRS-80 BASIC, which is a pretty low bar. Arc is inexplicably lacking trig, exp, and log, not to mention arrays and decent error reporting.)

To be sure, one could implement these libraries in Arc. The point is that implementing libraries detours you from the exploratory programming you're trying to do.

Paul Graham has commented that libraries are becoming an increasingly important component of programming languages, that huge libraries are now an expected part of a new programming language, and that libraries are an increasing important feature of programming languages. Given this understanding of the importance of libraries, it's surprising that Arc is so lacking in libraries. (It's also surprising that it lacks a module system or some other way to package libraries.) It's a commonplace complaint about Lisp that it lacks libraries compared to other languages, and Arc makes this even worse.

I think there are two different kinds of exploratory programming. The first I'll call the "Lisp model", where you are building a system from scratch, without external dependencies. The second, which I believe is much more common, is the "Perl/Python model", where you are interacting with existing systems and building on previous work. In the first case, libraries don't really matter, but in the second case, libraries are critical. The recently-popular article Programming in a Vacuum makes this point well, that picking the "best" language is fine in a vacuum, but in the real world what libraries are available is usually the key.

Besides the lack of libraries. Arc's slow performance rules it out for many of the algorithms from Programming Collective Intelligence. Many of the algorithms run uncomfortably slow in Python, and running Arc is that much worse. It's just not true that speed is unimportant in exploratory programming.

On the positive side for Arc, chapter 11 of Programming Collective Intelligence implements genetic programming algorithms by representing programs as trees, which are then evolved and executed. To support this, the book provides Python classes to represent code as a parse tree, execute the code tree, and prettyprint the tree. As the book points out, Lisp and its variants let you represent programs as trees directly. Thus, using Arc gives you the ability to represent code as a tree and dynamically modify the code tree for free. (However, it only takes 50 lines of Python to implement the tree interpreter, so the cost of Greenspunning is not particularly severe.)

To summarize, a language for exploratory programming should be concise, interactive, reasonably fast, and have sufficient libraries. Arc currently fails on the last two factors. Time will tell if these issues get resolved or not.

The importance of software testing

At work we have a nifty electronic postage kiosk that will weigh letters, compute the postage, print a postage strip, and bill a credit card all through a display and touch screen. When I tried using it to mail a letter, everything went fine until I got a Internet Explorer error dialog:

It's always a surprise when an embedded system reveals its inner workings. Somehow I assume such systems are built on some super-special technology, not HTML and Internet Explorer.

I should mention that I was just sending a letter to Canada. While this isn't the most common thing to do, it's not a particularly bizarre action either. And I definitely wasn't doing a sinister action such as sending a letter to the country of "DROP TABLE". (I should also mention that this blog posting has nothing to do with Arc, in case my regular readers are wondering.)

I started over with the kiosk and the same error dialog appeared again. At this point, I dismissed the dialog box via the touch screen and continued with Buy Postage. It displayed "Total Postage $NaN" (i.e. Not a Number). When it asked for my credit card, I hesitated briefly, I figured the worst case was I'd have to send them a check for 0/0; it's not like they were going to bill me +Infinity. Curiosity got the better of me and I decided to plunge forward in the interests of science. After I swiped my credit card, the kiosk printed a $0.69 postage strip, and gave me a receipt:

Sure enough, the receipt said my credit card had been charged $NaN. I can only imagine what the billing backend would make of that. I called my credit card company to check what really happened, but the day's transactions weren't available yet.

I see a couple morals to this story. The most obvious is that normal people don't swipe their credit cards through a machine offering to bill them $NaN. But the more relevant moral is that error checking and software testing is a good thing, especially when monetary transactions are concerned.

P.S. I emailed the kiosk support, and they assured me that the billing problems following a "system change" were resolved, and I'd be billed the proper $0.69.

Idioms for programming in Arc

The code that implements Arc illustrates many useful programming techniques. Some of the techniques occur multiple times, and can be considered idioms of Arc programming; techniques that can be applied to many problems. This article describes some of the most common idioms, and how they can be used in Arc programming. The techniques described focus largely on macros and recursion.

Macros

Not surprisingly, given Paul Graham's enthusiasm for macros, Arc makes heavy use of macros. A few idioms appear commonly in the code.

"Decorated body"

The most common use of macros in Arc is something I call the "decorated body", which wraps a chunk of body code with something to extend it, analogous to the decorator design pattern. Typically the decorator will set something up before executing the body code, as in w/outstring, w/table, and fromstring. (Note: the link for each operation goes to the documentation. Clicking on the code icon in the documentation will show the code for the operation.) The pattern is also used to set something up before execution and then clean up afterwards. This is especially useful for file operations, as in w/infile, w/outfile, and w/instring. These macros often have names starting with "w/", short for "with/", indicating what they are providing to the body. The HTML library makes heavy use of this idiom, for example in tag, form, and cdata, which wrap the body in various HTML opening and closing tags.

To examine the implementation of this idiom, consider let, which is defined as:

(mac let (var val . body)
  `(with (,var ,val) ,@body))

The typical features of this idiom are a macro definition with argument . body to pick up the remainder of the arguments, a macro definition starting with quasiquote `, and unquote-splicing ,@body to substitute the body code into the macro. The macro performs simple substitution:

arc> (macex1 '(let foo 42 body1 body2))
(with (foo 42) body1 body2)

Macro for control of evaluation

Unlike functions, macros receive their arguments unevaluated. This allows macros to be used for conditional execution of code, or to execute code multiple times iteratively. Some examples are when, unless, while, and for.

(You might expect if to be a macro. It is actually a built-in special form, since conditional macros need to be based on some underlying conditional form.)

The code for repeat illustrates that this idiom also uses the ,@body structure as "decorated body":

(mac repeat (n . body)
  `(for ,(uniq) 1 ,n ,@body))

Macro as lambda adapter

A variant of the body decorator is to use a macro to convert body code into a lambda function, which is similar to an adapter design pattern. This idiom is used when a function expects to receive a lambda function, but passing in body code is more convenient, especially when the base function is a Scheme primitive. Examples are thread, atomic, w/stdin, and w/stdout:

(mac w/stdout (str . body)
  `(call-w/stdout ,str (fn () ,@body)))

arc> (macex '(w/stdout foo body1 body2))
(call-w/stdout foo (fn nil body1 body2))

Macro to create functions with parameters

Another common macro idiom is to take a list of parameters and body code, and build a function out of these. This idiom is typically used to define a function that has special properties, and is often given a name that starts with "def". Some examples are rfn, afn, defmemo, defop, defopr, linkf, and rlinkf.

The code for defmemo shows the key component of this idiom: (fn ,parms ,@body) to build the function out of the parameters and body.

(mac defmemo (name parms . body)
  `(safeset ,name (memo (fn ,parms ,@body))))

Complex macros

One irony is that even though though macros are extremely powerful, most of the macros in Arc perform simple substitutions. There are, however, some macros that perform complex manipulation of their arguments. Assignment is built from the setform macro, which implements generalized variables through intricate macro processing of the arguments. Slightly less complex is and, which implements short-circuit evaluation by turning its arguments into nested if statements. Another interesting example is with; the macro splits up the arguments into variables and values:

arc> (macex '(with (a 1 b 2) (prn a b)))
((fn (a b) (prn a b)) 1 2)

The litmatch macro performs string matching by generating code to perform a sequence of character comparisons.

arc> (macex '(litmatch "abc" foo))
((fn (gs1442 gs1443) (unless (> (+ gs1443 3) (len gs1442))
  (and (is #\a (gs1442 (+ gs1443 0))) (is #\b (gs1442 (+ gs1443 1)))
       (is #\c (gs1442 (+ gs1443 2)))))) foo 0)

Recursion

Tail recursion is a standard Scheme technique for efficient recursion. If the last operation of a function is a recursive call, the compiler will use tail-call optimization to turn the recursion into iteration, avoiding creation of a stack frame on each call.

Iteration in Arc is built on top of tail recursion. Basic loop operations such as while, loop, and whilet use tail recursion on a function built from rfn:

(mac while (test . body)
  (w/uniq (gf gp)
    `((rfn ,gf (,gp)
        (when ,gp ,@body (,gf ,test)))
      ,test)))

cdr-scanning

A typical idiom for scanning a list is to tail-recursively call the function on the cdr of the list. Some examples are reclist, nthcdr, last, and rev.

The code for assoc illustrates this idiom. If there is no match, assoc is called on the cdr, until the whole list has been scanned:

(def assoc (key al)
  (if (atom al)
       nil
      (and (acons (car al)) (is (caar al) key))
       (car al)
      (assoc key (cdr al))))

Tail-recursive string functions

One idiom in Arc for using tail recursion with strings is to add an index parameter to the function. This index parameter indexes into the string, and by incrementing it in each call, the function can be made tail-recursive and doesn't require modifying the string. The index parameter is often made an optional parameter so "normal" uses of the function don't need to specify the index. Some examples of this idiom are recstring, findsubseq, indented-code, parabreak, and urlend.

The code for headmatch illustrates this idiom; in this case the tail-recursion uses an anaphoric function:

(def headmatch (pat seq (o start 0))
  (let p (len pat) 
    ((afn (i)      
       (or (is i p) 
           (and (is (pat i) (seq (+ i start)))
                (self (+ i 1)))))
     0)))

Recursion with cons

Many operations in Arc need to perform operations on a sequence and create a result list. The common Arc idiom is to recurse through a sequence, building up the result with cons. Specifically, a macro (op seq) will return the cons of something done to (car seq) and (op (cdr seq)). Thus, op recursively steps through seq, processing an element at a time and building up the result. This idiom provides an interesting contrast to the previous recursion examples because this idiom is not tail-recursive. Because the cons is applied to the result of the recursive function call, tail-call optimization cannot be applied. Several examples of this idiom are join, rem, reinsert-sorted, pair, firstn, firstn-that, tuples, and range.

The code for map1 illustrates this idiom:

(def map1 (f xs)
  (if (no xs) 
      nil
      (cons (f (car xs)) (map1 f (cdr xs)))))

Note that f is applied to (car xs), map1 is called recursively on (cdr xs), and the two are cons'd together.

Miscellaneous

The majority of the idioms I discuss are based on macros or recursion. This secion discusses some miscellaneous idioms that don't fit those categories.

Push and reverse

The "push and reverse" idiom is an efficient, but somewhat surprising way to generate a list. In this idiom, successive elements are pushed onto the front of the list, and when the entire list is generated, it is reversed to obtain the desired order. This is a well-known Lisp idiom and is more efficient than the obvious method of appending elements to the end of the list. Several examples of "push and reverse" are drain, dedup, parse-format, litmatch, endmatch, and handle-post.

The code for n-of illustrates the idiom. Items are added with push to an accumulator (ga in this case), and the accumulator is reversed with rev at the end:

(mac n-of (n expr)
  (w/uniq ga
    `(let ,ga nil     
       (repeat ,n (push ,expr ,ga))
       (rev ,ga))))

String stdout

Arc makes extensive use of an idiom I'll call "string stdout" because a string is used as stdout. The code writes multiple chunks to stdout, and the results are gathered into a string. This idiom avoids having to manually concatenate the components into the result string. The tostring macro is used to implement this idiom. Arc has a surprisingly large number of macros that use this idiom, including readline, code-block, unmarkdown, varfield, markdown, eschtml, striptags, parafy, subst, multisubst, and num.

Typically, code using this idiom will use produce output with pr or writec, and use tostring to collect the output. The code for multisubst illustrates this:

(def multisubst (pairs seq)
  (tostring 
    (forlen i seq
      (iflet (old new) (find [begins seq (car _) i] pairs)
        (do (++ i (- (len old) 1))
            (pr new))
        (pr (seq i))))))

The flip side of this idiom is the "string stdin" idiom, where a string is used as stdin. The "string stdin" idiom is rarely used; one example is parse-format.

Summary

The Arc code illustrates several common Arc idioms, some of which are well-known Scheme or Lisp idioms. Since Paul Graham is a Lisp expert, carefully studying his Arc code is a rewarding way to learn more about programming Lisp-like languages.

Undoubtedly I've missed some important idioms. Please let me know if your favorite idiom is missing, or if I've mangled the descriptions of any idioms.

Many Arc compilers and interpreters

The introduction of the Arc language has spawned a mini-boom of Arc compilers and interpreters implemented in everything from JavaScript to .NET. Because Arc is a fairly simple Lisp dialect, it is relatively straightforward to implement, and many people are using it to learn about compiler and interpreter design, and to showcase different implementation techniques and languages.

Paul Graham's official distribution started it all, of course. This version is implemented in MzScheme and translates Arc into Scheme code. The writeup on Arc Internals provides more information on how it is implemented.

The Arc Forum is the site of most of the unofficial Arc development effort. The "Anarki" branches of Arc on github consist of a "stable" bug-fixed version of official Arc, and a more exploratory version with many modifications. (For information on using github, see Brief Guide to Anarki and Git.

Anarki includes "ac.sbcl.lisp", an implementation of Arc in SBCL. It implements closures using CPS (Continuation-passing style) transformations, but doesn't include threads or networking according to the brief description.

Perhaps the first reimplementation of Arc was ArcLite, which is Arc ported to JavaScript. This version of Arc is unique because it runs in the browser. The running version can be accessed online. It provides a subset of functionality, omitting tail-call optimization, continuations, and various operations.

Rainbow (l'arc en ciel in French) is an implementation of Arc in Java. It is fairly complete, providing continuations and tail-call optimization according to the description. It is available at github.

An Arc compiler for .NET has been developed, based on the MBase compiler prototyping framework. The description states that it implements a subset of Arc, but is much faster than standard Arc. It is available from Meta Alternative.

Currently under active development is "arc2c", which compiles Arc to C. Current status is at arclanguage.org. This compiler is intended to be a full, high-performance implementation of Arc. It uses CPS transformations to implement continuations. It uses the Boehm garbage collector. arc2c is available at github.

CL-Arc is a proposal to compile Arc to Common Lisp; work hasn't started on it yet.

Many of these Arc implementations actively welcome participation. The future is likely to hold continuing improvement in the quality, functionality, and performance of Arc implementations, as well as surprising and unusual variants.

Ajax and Arc

Ajax is surprisingly easy to use with the Arc language. This article shows how to implement Ajax-based autocompletion and dynamic page updates using the script.aculo.us and Prototype JavaScript frameworks. These frameworks allow Ajax applications to be implemented with just a few lines of additional code. The hard work is done by the script.aculo.us and Prototype libraries. All the Arc code needs to do is provide the list of autocompletion candidates, and the dynamic page content.

The example

This example implements a simple Ajax input autocompleter and dynamic page update. For the autocompleter, as soon as you enter a few letters into the input, it provides a list of matching terms. As soon as you select a term, the page is dynamically updated with associated data, as in the following screenshot:

For the purposes of the demonstration, the content is information on the countries of the world, obtained from the CIA World Factbook.

To summarize how it all works: When you enter characters in the input field, the script.aculo.us autocompleter JavaScript sends the charaters to the Arc server, which returns the autocomplete suggestions. The autocompleter JavaScript displays the suggestions on the page. When you select a country, the updater JavaScript does three separate requests to the Arc server, to request the population, area, and capital. When the responses arrive, they are inserted into the page.

In more detail, the autocompletion is performed by Ajax.Autocompleter, and the dynamic updating is performed by Ajax.Updater. The control flow is:

• The Ajax.Autocompleter associated with the autocomplete input and autocomplete_choices div sends inputs to /auto_complete?prefix=chars.
• The Arc handler sends back a formatted list of autocomplete candidates, e.g. <ul><li>Iran</li><li>Iraq</li><li>Ireland</li></ul>.
• The Ajax.Autocompleter displays the candidates in the autocomplete div.
• When an autocompletion is selected, the update JavaScript function starts three Ajax.Updater instances, which send an Ajax request to URL /getcontents?field=population&name=value, and similarly for area and capital in parallel.
• The Arc handler for getcontents returns the desired contents.
• Ajax.Updater puts the contents into the contents div.

Running the example

First set up the necessary files.

• Download ajax.zip and uncompress it into the same directory that Arc runs in. This zip file provides ajax.html, ajax.arc, data.arc, and autocomplete.css.
• Download the script.aculo.us library files from script.aculo.us. Copy the .js files from lib and src into the same directory that Arc runs in.

Next, start up the Arc interpreter, load the ajax.arc file, and start the web server.

arc> (load "ajax.arc")
arc> (thread (serve 8080))
arc> ready to serve port 8080

Then go to http://localhost:8080/ajax.html. (Unfortunately I don't have a live demo on a public machine. If anyone sets one up, let me know and I'll add a link here.)

Start typing in the box, and you should see a dropdown with autocompleted choices. Click one, and the code will be displayed below asynchronously.

The Arc code

The Arc server code is in ajax.arc. Two Arc handlers are implemented to provide the client-side Ajax support. The first, auto_complete receives the current input contents and returns a list of up to 10 autocompletion candidates formatted in HTML. The second handler, getcontents returns the dynamic content for the page, from the database table. Note that the handlers do nothing particularly special to make them "Ajax"; they are standard Arc web handlers based on defop and can be accessed directly through the browser. See Arc Web Server for more information on web serving with Arc.

(defop auto_complete req
  (let prefix (downcase (arg req "prefix"))
    (prn (to-html-list (cut (startselts prefix keylist) 0 10)))))

(defop getcontents req 
  (with (field (arg req "field")  name (arg req "name"))
    (if (is field "population") (prn ((database name) 1))
        (is field "area") (prn ((database name) 2))
 (is field "capital") (prn ((database name) 3)))))

The handlers use a couple helpers; startselts returns the elements that match the autocomplete prefix and to-html-list wraps the elements in HTML list tags.

; Returns a list of elements that start with prefix
(def startselts (prefix seq) (rem [no (begins (downcase _) prefix)] seq))

; Wraps elts in HTML list tags
(def to-html-list (elts) (tostring
  (prall elts "<ul><li>" "</li><li>")
  (pr "</li></ul>")))

The actual content is obtained from data.arc, which contains the information on each country as a list of lists.

("United States" "301,139,947" "9,826,630" "Washington, DC")

Some simple code converts the list into a table called database indexed by country for easy lookup, and generates a sorted list of countries for use in autocompletion:

(= database (table))
(w/infile inf "data.arc"
  (let datalist (sread inf nil)
    (each elt datalist
      (= (database (elt 0)) elt))))
(= keylist (mergesort < (keys database)))

For some reason, the default Arc web server srv.arc doesn't support .js files. The ajax.arc file modifies the server slightly to support these files:

(= (srv-header* 'text/javascript) 
"HTTP/1.0 200 OK
Content-Type: text/javascript; charset=UTF-8
Connection: close")

(def static-filetype (sym)
  (let fname (string sym)
    (and (~find #\/ fname)
         (case (last (check (tokens fname #\.) ~single))
           "gif"  'gif
           "jpg"  'jpg
           "css"  'text/css
           "txt"  'text/html
           "html" 'text/html
           "js"   'text/javascript
           ))))

Debugging

Several things can go wrong when trying to run the example. If the initial page doesn't load at all, something is probably wrong with the Arc server. If no autocompletion happens, the JavaScript may not be loading, or the Arc server may have problems. If the autocompletion shows up as a bulleted list, the CSS file is probably not loading.

The Arc code can be debugged in several ways. The first is to access the handlers directly. The autocomplete handler http://localhost:8080/auto_complete?prefix=a should return a bullet list of autocomplete suggestions. The contents handler: http://localhost:8080/getcontents?field=area&name=Algeria should return the dynamic contents value.

The Arc code can also be debugged by strategically inserting print statements such as:

(write req (stderr))

This will display the request on the Arc console.

To debug Ajax, you can use Firefox plugins Live HTTP Headers and Firebug. Live HTTP Headers lets you see the headers between the browser and the server, and is very helpful to determine if something is failing. Firebug allows much more in-depth JavaScript debugging. The browser's JavaScript console is also useful to see JavaScript errors.

This article has just scratched the surface of script.aculo.us and Ajax. More information is available at the script.aculo.us website or in books.

Documentation of HTML generation in the Arc language

I've created documentation of Arc's HTML generation operations (from arc.arc). There are a lot of different functions there, but I've tried to cover them all.