If you've programmed in Arc, you've probably noticed that the error messages are often cryptic at best. Error handling is a major weakness of the current Arc implementation; I've wasted a lot of time trying to figure out why my code fails, because the error message has no connection to the actual problem.
This article gives examples of some mysterious error messages, how they arise, and what they mean. Hopefully this can save some debugging time.
Usually Arc doesn't provide any indication of where the error occurred. In the cases where Arc does provide location information, the location is a byte offset, not a line number, which is hard to interpret:
arc> (load "t.arc")
Error: "t.arc::720: read: expected a ')'"
If you're loading a file, how do you find byte offset 720? One way is dd if=t.arc bs=1 skip=720 which will display the file from the 720th character onward.
Similar errors can be generated from REPL input. In this case, the unexpected parenthesis is at character 910 that's been typed to the REPL (although that's unlikely to be useful):
arc> (def foo (a (b c)) (prn a))
arc> (foo 1 2)
Error: "car: expects argument of type <pair>; given 2"
Destructuring bind fails because argument format doesn't match function definition.
arc> (def f (o x (table)) (prn x))
arc> (f 42)
Error: "car: expects argument of type <pair>; given ()"
You need two sets of parentheses in the def, one around the arguments, and one around the optional argument:
arc> (def f ((o x (table))) (prn x))
arc> (+ 1 "s")
Error: "+: expects type as 2nd argument, given: \"s\"; other arguments were: 1"
Straightforward: wrong type to +.
(= t 42)
Error: "Can't rebind t"
The atoms t and nil can't be changed. Don't use t as a variable.
arc> (map (prn) '(a b c))
Error: "Function call on inappropriate object nil (a)"
You need to pass a function to map, such as prn or [prn _] rather than (prn)
arc> (car "abc")
Error: "Can't take car of \"abc\""
Car and cdr don't work on strings. You'll also get this error if the function erroneously uses car on a string internally:
arc> (counts "abc")
Error: "Can't take car of \"abc\""
arc> (with a 4 (+ a 1))
Error: "Can't take cdr of a"
The mysterious "can't take cdr" error shows up if you don't have parentheses around the variable assignments. You may be thinking of let, which doesn't use the parentheses and assigns a single variable.
Let me know if you have any other candidates for mystery errors.
Since I've been hearing good things about the F# language from various people, I wanted to give it a try, but I wasn't interested in spending $250 on Microsoft Visual Studio. It turns out, however, that you can run F# for free in several ways.
F# with Visual Studio Shell
On Windows, you can run F# with a complete IDE by using Visual Studio Shell (not to be confused with Visual Studio or Visual Studio Express). Visual Studio Shell is an IDE without any included languages, and is available for free.
Installation
(Instructions updated August 2009 for latest versions.)
Run the download. Note: this download does not install Visual Studio Shell; it unpacks a "redistributable package" for Visual Studio Shell that contains the installer. Don't ask why. Make sure you note where it puts this, probably C:\VS 2008 Shell Redist\Integrated Mode.
Run the Visual Studio Shell installer vside.enu.exe that was unpacked above. Important: you must not have F# installed at this point; if you already have it installed, uninstall it first.
Make sure Microsoft Visual Studio 2008 shows up in your Start menu.
Start Visual Studio Shell. Start F# should appear under View -> Other Windows -> F# Interactive; Control-Alt-F should also work.
Type into the F# Interactive window:
printfn "Hello world!";;
Hello world!
val it : unit = ()
Note that in the interactive window, you must enter ;; to have your input processed.
To see the F# tutorial, click "Create Project ..." in the "Recent Projects" window, then double-click "F# Tutorial".
To create a new program, click "Create Project ..." in the "Recent Projects" window, then double-click "F# Application". Type code into the "Program.fs" window, for example:
printfn "Hello world!"
open System
Console.ReadKey(true) |> ignore
To run the program, hit F5. The purpose of the last two lines is to keep the
console window open until you hit a key; otherwise, the window will only flash
up briefly. Note that the double-semicolons aren't required.
You can also highlight text in the program window and press Alt-Enter to have it executed in the F# Interactive window. Visual Studio includes a debugger with breakpoints and all. Select Debug -> Start Debugging to run under the debugger.
F# from the Windows command line
You can also skip Visual Studio and run F# from the command line. To do that, just download F# as above. Then run the F# interpreter fsi.exe either from a cmd window or from the Start menu:
C:\Program Files\FSharp-1.9.6.2\bin\fsi.exe
> printfn "Hello world!";;
Hello world!
val it : unit = ()
F# with Mono
Another option is running F# with Mono. This provides a way to run F# on Linux or OS X. To do this, download and unzip F# 2008 CTP (zip). Download and install Mono 2.X. The Readme file in the F# distribution provides all the details on running F# with Mono, so look there.
(I wasn't too successful with Mono; it's no longer supported on RedHat, and compiling from sources ran into libgdiplus incompatibility. I could only run fsi.exe with the --no-gui flag.)
F# vs Arc
Since this is nominally an Arc blog, I should compare F# and Arc. The F# language has some nice features such as type inference, currying, and pattern matching. On the other hand, it lacks powerful Lisp-style macros, and is not as terse as Arc. The F# implementation is much, much more polished than Arc. It has extensive documention, an IDE, real error messages, reasonable performance, huge libraries, a compiler, and so forth. Overall, I find programming in F# more enjoyable than in Arc, and find it easier to get something done in F# after using it for a few hours than in Arc after several months.
Next steps
Once you have F# running, you can take a look at Microsoft's F# in 20 Minutes tutorial to learn more. I'm currently going through the book Expert F#.
One of the interesting things about F# is you can easily write graphical Windows applications. A couple quick hints: to use the Windows Forms dlls, go to "Project -> Add Reference" and click "System.Windows.Forms", and then "ok". To suppress the console window, go to "Project -> ConsoleApplication2 Properties..." and select "Output type: Windows Application".
I found (and I realize this is an obvious lesson) that I learned much more from actually writing simple F# programs than from reading blog posts about it. So if you're still reading, stop now, install F#, and write some code!
I was recently reading
The Little Schemer, a very intersting book about how to think in Scheme. The book uses a unique question-response style to present simple concepts such as cons and recursion, as well as complex concepts such as using lambda functions to build arithmetic out of fundamental axioms, and deriving the Y Combinator.
As you're probably aware, the Y Combinator is a fixed-point combinator, which lets you build recursion out of an anonymous, non-recursive function. The tricky part of building recursion without naming is that if you can't name a function, how can the function call itself? The Y Combinator is a way to do this.
In Arc, it's easy to write a recursive factorial function:
(def fact (n)
(if (is n 0) 1
(* n (fact (- n 1)))))
Note that def assigns the name fact to this function, allowing it to recursively call itself. But without def, how can the function call itself?
Fixed point as an infinite stack of function calls
Let's make a function fact-gen that if passed the factorial function as input, returns the factorial function. (Note that fn is Arc's equivalent of lambda.)
(def fact-gen (fact-in)
(fn (n)
(if (is n 0) 1
(* n (fact-in (- n 1))))))
This may seem rather useless, returning the factorial function only if you already have it. Since we don't have a factorial function to pass in, we'll pass in nil (technically bottom). This at least gets us started:
We can compute factorial of 0, but factorial of 1 hits nil and dies. But we can take our lame factorial function, pass it in to fact-gen and get a slightly better factorial function that can compute factorials up to 1:
arc> ((fact-gen (fact-gen nil)) 1)
1
We can repeat this to get an even more useful factorial function:
If we could have an infinite stack of fact-gen calls, then we would actually have the factorial function. But we can't do that. Or can we?
The fixed point of a function f is a value x for which f(x) = x. We can apply the same idea to our infinite stack of fact-gen. Since applying fact-gen to the infinite stack one more time makes no difference, (fact-gen infinite-stack) = infinite-stack, so the infinite stack is a fixed point of fact-gen. Thus, the fixed-point of fact-gen is the factorial function.
If taking the fixed point of an algorithmic function seems dubious to you, a full explanation is available in Chapter 5 of the 1300 page tome Design Concepts in Programming Languages; trust me, it's all rigorously defined.
The fixed-point combinator
So how do you find the fixed point without an infinite stack of functions? That's where the fixed-point combinator (also known as the Y combinator) comes in. The fixed-point combinator Y takes a function and returns the fixed point of the function. That is, applying the function once more makes no difference:
y f = f (y f)
You may wonder how the Y combinator computes an infinite stack of functions. The intution is it computes a finite stack that is just big enough for the argument.
The fixed-point combinator in Haskell
In Haskell, you can use the above definition of the Y combinator directly:
y(f) = f (y f)
fact f n = if (n == 0) then 1 else n * f (n-1)
y(fact) 10
This is a bit of a "cheat", since the definition of the y combinator takes advantage of Haskell's pre-existing recursion, rather than providing recursion from scratch. Note that this only works because of lazy evalation; otherwise the definition of y is an infinite loop. (Haskell includes the Y combinator under the name fix.)
The Y combinator in Arc
The Little Schemer derives the Y combinator in Scheme. The Arc version is very similar:
If the Y combinator is applied to the earlier fact-gen, it yields a recursive factorial function. Like magic:
arc>((Y fact-gen) 10)
3628800
You may protest that this doesn't really implement anonymous recursion since both Y and fact-gen are explicitly named with def, so you could really just call fact-gen directly. That naming is just for clarity; the whole thing can be done as one big anonymous function application:
Now you can see the recursive factorial can be computed entirely with anonymous functions, not a def in sight. The first blob is the Y combinator; it is applied to the second blob, the factorial generator, and the resulting function (factorial) is applied to 10, yielding the answer.
Y Combinator in Java
The Y combinator in a Lisp-like language is not too tricky. But I got to wondering if it would be possible to implement it in Java. I'd done
crazy continuation stuff in Java, so why not the Y combinator?
Several objections come to mind. Java doesn't have first-class functions. Java doesn't have closures. Everything in Java is an object. Java is statically typed. Is the idea of a Y combinator in Java crazy? Would it require total Greenspunning?
To implement the Y combinator in Java, I did several things. Since Java doesn't have first-class functions, I wrapped each function in an anonymous inner class with a single method apply(), which executes the function. That is, I used a function object or functor.
Since "objects are a poor man's closures" (Norman Adams), I used this object creation in place of each closure.
In order to define types, I restricted my Java Y combinator to integer functions on integers. Each type defines an interface, and each object implements the appropriate interface.
Using these techniques, I was able to fairly directly implement the Y combinator in Java. The first part defines a bunch of types: IntFunc is a simple function from integers to integers. IntFuncToIntFunc is the type of the factorial generator, taking an integer function and returning another integer function. FuncToIntFunc is the somewhat incomprehensible type of the Y combinator subexpressions that apply f to f yielding an integer function. Finally, the Y combinator itself is an IntFuncToIntFuncToIntFunc, taking an IntFuncToIntFunc (fact-gen) as argument and returning an IntFunc (the factorial function itself).
class YFact {
// Integer function returning an integer
// int -> int
interface IntFunc { int apply(int n); }
// Function on int function returning an int function
// (int -> int) -> (int -> int)
interface IntFuncToIntFunc { IntFunc apply(IntFunc f); };
// Higher-order function returning an int function
// F: F -> (int -> int)
interface FuncToIntFunc { IntFunc apply(FuncToIntFunc x); }
// Function from IntFuntToIntFunc to IntFunc
// ((int -> int) -> (int -> int)) -> (int -> int)
interface IntFuncToIntFuncToIntFunc { IntFunc apply(IntFuncToIntFunc r);};
Next comes the meat. We define the Y combinator, apply it to the factorial input function, and apply the result to the input argument. The result is the factorial.
public static void main(String args[]) {
System.out.println(
// Y combinator
(new IntFuncToIntFuncToIntFunc() { public IntFunc apply(final IntFuncToIntFunc r) {
return (new FuncToIntFunc() {public IntFunc apply(final FuncToIntFunc f) {
return f.apply(f); }})
.apply(
new FuncToIntFunc() { public IntFunc apply(final FuncToIntFunc f) {
return r.apply(
new IntFunc() { public int apply(int x) {
return f.apply(f).apply(x); }});}});}}
).apply(
// Recursive function generator
new IntFuncToIntFunc() { public IntFunc apply(final IntFunc f) {
return new IntFunc() { public int apply(int n) {
if (n == 0) return 1; else return n * f.apply(n-1); }};}}
).apply(
// Argument
Integer.parseInt(args[0])));
}
}
The result is the factorial of the input argument: (source code)
$ javac YFact.java
$ java YFact 10
3628800
Surprisingly, this code really works, implementing the Y combinator. Note that there are no variables (apart from arguments), and no names are assigned to any of the anonymous functions. Yet, we have recursion.
The Java version is considerably more verbose than the Arc version, since each function becomes an object creation wrapping an anonymous function declaration, with a liberal sprinkling of type declarations, public and final. Even so, there is a direct mapping between the Arc code and the Java code. There's no Greenspunning in there, no Lisp simulation layer. Ironically, the Java code starts to look like Lisp code, except with a bunch of }}} instead of ))).
To convince you that the Java recursion works even in a more complex case, we can implement Fibonacci numbers by simply replacing the input function: (source code)
...
// Recursive Fibonacci input function
new IntFuncToIntFunc() { public IntFunc apply(final IntFunc f) {
return new IntFunc() { public int apply(int n) {
if (n == 0) return 0;
else if (n == 1) return 1;
else return f.apply(n-1) + f.apply(n-2); }};}}
...
The code recursively generates Fibonacci numbers:
$ java YFib 30
832040
Is this the "real" Y Combinator?
The typical form of the Y combinator is:
λf.(λx.f (x x)) (λx.f (x x))
and you may wonder why the Y combinator in Arc and Java is slightly different. Because Java (and Scheme, Arc, etc.) are call-by-value languages and not call-by-name languages, they require the applicative-order Y combinator. This combinator has the form:
λr.(λf.(f f)) λf.(r λx.((f f) x))
The call-by-name Y combinator will go into an infinite loop in a call-by-value language. I found this out the hard way, when I implemented the "wrong" Y combinator in Java and quickly got a stack overflow.
For details on applicative-order, eta-reduction, why different combinators are required, and a derivation of the Y combinator, see
Sketchy Lisp.
Java vs. Lambda Calculus
In the Java code, new takes the place of λ and apply explicitly shows application, which is implicit in lambda calculus. To make the connection between the Java code and the lambda expression clearer, I have highlighted the key parts of the Java Y combinator:
// Y combinator
(new IntFuncToIntFuncToIntFunc() { public IntFunc apply(final IntFuncToIntFunc r) {
return (new FuncToIntFunc() {public IntFunc apply(final FuncToIntFunc f) {
return f.apply(f); }})
.apply(
new FuncToIntFunc() { public IntFunc apply(final FuncToIntFunc f) {
return r.apply(
new IntFunc() { public int apply(int x) {
return f.apply(f).apply(x); }});}});}}
Note the exact correspondence of the highlighted parts with the lambda calculus expression:
λr.(λf.(ff)) λf.(rλx.((ff) x))
Conclusion
It is possible to implement the Y combinator in Java, showing that Java has more power than many people realize. On the other hand, the Java code is ugly and bulky; a Lisp-like language is a much more natural fit.
For more fun, try going through SICP in Java.
Postscript
I received some great feedback with interesting links. Apparently a number of people enjoy implementing the Y combinator in a variety of languages:
When using the Arc REPL, I've often wanted to edit a previous line. Python lets you access and edit lines using the arrow keys, so why not Arc? You can do this with Arc by using rlwrap and the GNU Readline library. (Not to be confused with Arc's readline I/O operation.)
Readline provides many editing operations. If you're not an Emacs user, you'll probably want to use the arrow keys to move through your current line and history, Home and End to move to the beginning and end of the line, and Delete or Backspace to delete characters. Another useful feature is Control-underscore will undo an edit. If you enter a closing parenthesis, Readline will flash the corresponding opening parenthesis, which is helpful when entering Arc code. Control-R followed by text will search your history for a line containing that text. Readline supports the standard Emacs keybindings. For instance, Control-B and Control-F to move backwards and forward, Meta-B and Meta-F to move by words, Control-K kills (erases) to the end of the line, Control-Y yanks killed text back into the line, and so on. See the documentation for the full documentation.
Installing rlwrap
But how do you use readline with Arc? There has been discussion at arclanguage.org, but there are complications. Mzscheme added support for readline in version 360, but Arc inconveniently runs on version 352. Backporting readline to 352 doesn't work cleanly.
The easiest way is to install the rlwrap command, which wraps an arbitrary command in readline. To install it on Linux, run sudo yum install rlwrap or sudo apt-get install rlwrap as appropriate.
For Windows, rlwrap is part of cygwin, although you need to explicitly select in the installer under "Select Packages to Install"; it's under "Utils -> rlwrap".
Once installed, add rlwrap in front of your mzscheme command. For instance:
rlwrap mzscheme -m -f as.scm
More ways of running rlwrap with Arc are described in the arclanguage.org discussion.
Once you have rlwrap installed, you should find entering Arc code to be much easier.
In a Caesar cipher, each character in the plaintext is shifted by a fixed amount. For instance, if the shift is 3, "a" becomes "d", "b" becomes "e", and so on. In the Vigenère cipher, multiple shifts are used. For instance, if the key is (2, 4, 9), the first character is shifted by 2, the second character is shifted by 4, the third character is shifted by 9. The pattern then repeats with shifts of 2, 4, 9, 2, 4, 9, and so on until the entire plaintext is encrypted. Note that the length of the key is arbitrary.
The encrypted string of the reddit cipher can be expressed in Arc as:
(= s "t/GlC/,@RiG.^(xBQ2.MslF27@w#xXw,KHx,/9xiU-(!\"ixf%\";iA-=@wiW-=6EnRX#,stL-\"6Mqy!6:HDf#,6LDA0,)LoS9@:slPY9!xmx!?/LiM,,MsjL16@xCx.,6zrT26:HDx-$,svM/,6MnQ!P6sXz#/%NBJ^6jsly,6#ttCX/+sjx9/+MuCX8/MiFY(.xAx$/+AxS!69AjL4/$ziR5,6tuE-(/MqKC")
The first thing we can do is determine how long the key is. Since the key repeats, it is likely that characters in the ciphertext will also repeat with the same frequency. We can apply a simple autocorrelation function:
(def autocorrelate (s offset)
(let total 0
(for i 0 (- (len s) offset 1)
(if (is (s i) (s (+ i offset)))
(++ total)))
total))
This function will compare each character with the character offset later in the string, and count the number of matches. Let's find the best value for offset:
Note that comparing each character with the character 6 characters later has 16 matches, which is much better than the other offsets. So it's pretty likely that the key is length 6. (There are also spikes at multiples of 6, as you'd expect.)
Now let's make a function to decode an encrypted character given an offset. We need the algorithm's character set mapping m used to shift the characters. The typical Vigenère uses a character set of 26 letters, but the challenge algorithm uses a much larger character set. To decode a character, we look it up in the mapping to get an integer index, shift by the offset, and convert back to a character.
(= m " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.,-\'?/\\!@#$%^*()+=~\";:")
(def decodechar (ch offset)
(m (mod (- (pos ch m) offset) (- (len m) 1))))
For example, if our characters were shifted by 3, "D" should decode as "A":
(decodechar #\D 3)
#\A
At this point, there are multiple approaches to break the cipher. If you have any known plaintext, you can immediately get the key. Without a known plaintext, you can take an expected plaintext such as " the " and drag it through the ciphertext, generating a presumtive key at each point. If the same pattern pops out in several places, you may have the key.
Alternatively, if we take every 6th character in the ciphertext, we have 6 Caesar cipers, and we can break each one separately. Breaking a Caesar cipher is easy. One approach is frequency analysis; assuming there are more e's and t's than q's and z's in the plaintext, you can compute the likelihood of each key. Log-likelihood is a typical way, but Arc doesn't have a log function, annoyingly enough.
I decided to take a more brute force approach. I made a function that prints out the decoding of one of the Caesar substrings given an offset value.
(def decodesubstring (s startpos skip offset)
(loop (= i startpos) (< i (len s)) (= i (+ i skip))
(pr (decodechar (s i) offset)))
(prn))
For instance, to take every sixth character, starting with the second, and shift it by 35:
(decodesubstring s 2 6 35)
"i$/#b$UV#=/d;cc/$c/$^;/d/e/\/dd$**^\d
That deciphering doesn't look too good if we're looking for English text. Either our plaintext is a Perl program or 35 is the wrong offset. Let's brute-force try all the offsets:
Looking this over, it's pretty obvious that offset 19 yields normal English letters, punctuation, and spacing, and everything else doesn't. (Of course, since we're only looking at every sixth letter, the result isn't readable.) We can repeat this for the other positions in the string
(testall s 0 6)
...
59 SepdaVirouumw eelche e ne?i iibri ier
...
(testall s 1 6)
...
59 ilr,leckwl e y syki,l ye oImttidtcn i
...
By scanning the six sets of outputs, the obvious key set is (59 59 19 9 24 50).
Now we can write a simple function to decrypt the entire string from a list of offsets:
(def decode (s offsets)
(for i 0 (- (len s) 1)
(pr (decodechar (s i) (offsets (mod i (len offsets))))))
(prn))
(decode s '(59 59 19 9 24 50))
Sincerely impressed, cheald. Very nice work. Now, could you let me know that you've successfully cracked this one, and let me give you one more test? Obviously I can make it a little bit harder without changing the algorithm.
The original algorithm uses a string for the key, not integers, so we can map the offsets back to a string key:
(each x '(59 59 19 9 24 50) (pr (m x)))
66sixXnil
Ignoring nil, the key is "66sixX". Thus, a few minutes with Arc is sufficient to break the cipher and determine the original key.
The reddit thread includes multiple other challenges. One is:
The same technique finds the key length is 9, the offsets are (57 20 20 56 13 16 20 56 4), and the plaintext and key are:
(decode s2 '(57 20 20 56 13 16 20 56 4))
This is basically just a bunch of jibberish text, though certainly able to be read, so that chneukirchen may test out this encryption method. If he succeeds well done! I sincerely congratulate him. If he does not I ask that at least he not continue to make fun of this cipher which is so easy a "7 year old" could crack it, or "it can be cracked by hand" according to others. Let me repeat once more I know it CAN be cracked, but I bet MOST people (reddit is not "most people") won't do it.
(each x '(57 20 20 56 13 16 20 56 4) (pr (m x)))
4tt3mpt3dnil
This shows how Arc can be used as a tool in simple cryptanalysis, and also shows that homegrown cryptography can be very weak. If you're interested in cryptography, I highly recommend that you read Applied Cryptography. If it's the history of cryptography that interests you, I recommend The Codebreakers.
The total world's population of Haskell programmers fits in a 747.
And if that goes down, nobody would even notice.
-- Erik Meijer
I recently saw an interesting talk on functional programming by Erik Meijer (of Bananas, Lenses, Envelopes, and Barbed Wire fame). Among other things, he discussed why many superior technologies such as Haskell don't catch on.
Geek formula for success
He claims the "Geek formula" for success of a technology is that if a technology is 10 times better, it should catch on and become popular. Even if it is slower, Moore's law will soon make it 10 times faster.
So if Haskell is 10 times better than C and Haskell programs are 10 times shorter, everybody should be using Haskell.
Real-life formula for success
However, as Erik points out, "That's not how it is in real life." In real life, success is based on the perceived crisis divided by the perceived pain of adoption. Users want something that will get the job done and solve their crisis, without a lot of pain to switch.
This argument applies to many languages that remain unpopular despite their technical merits, such as Lisp, Arc, and Erlang, as well as technologies such as the Semantic Web and LaTex.
The Change Function
The above argument is based on the book The Change Function: Why Some Technologies Take Off and Others Crash and Burn by Pip Coburn. To summarize the book, new technologies aren't adopted because they are great, new, and disruptive; they are adopted only if the user's crisis solved by the technology is greater than the perceived pain of adoption. As a result, most new technologies fail.
The first half of the book is a bit fluffy, but gets more interesting when it discusses specific technologies that failed or succeeded. The book also goes out on a limb and predicts future winners (mobile enterprise Email, satellite radio, business intelligence software) and losers (RFID, entertainment PC, WiMax).
Languages and The Change Function
The Change Function argument has a lot of merit for explaining what languages become popular and what languages don't.
If Lisp is so great, why are there 8 million Visual Basic programmers worldwide and few Lisp programmers? The answer isn't pointy-haired bosses (since Lisp isn't popular on SourceForge either). The crisis vs. pain of adoption model provides a powerful explanation:
Magnitude of crisis solved by Visual Basic: High (e.g. how to easily write Windows applications)
Total Perceived Pain of Adoption for Visual Basic: Very Low (hit Alt-F11 in Excel and you're done)
Magnitude of crisis solved by Lisp: Low (metaprogramming, powerful macros, and higher-order functions are solutions in search of problems)
Total Perceived Pain of Adoption for Lisp: High (this shouldn't require explanation)
The same model explains the success of, for instance, Java:
Magnitude of crisis solved by Java: High (originally how to run code in a browser and write portable code, now how to avoid crashes due to memory allocation errors and bad pointers)
Total Perceived Pain of Adoption: Low (syntax similar to C++, easy to deploy)
Applying this model to other languages is left as an exercise for the reader.
Erik points out that Erlang and Haskell are now being marketed according to the second formula: there is a multicore crisis and functional languages are the solution. It will be interesting to see how much additional traction these languages get without addressing the "pain of adoption" part.
The Change Function and startups
The Change Function ends with ten sets of questions and a set of techniques for designing technologies that will be adopted; this part of the book has many ideas that would be beneficial for startups. Many of these are fairly obvious, such as "Fail fast and iterate", and have a customer-centered culture instead of a sales-centered culture, while others are more thought-provoking: "What is the user crisis you intend to solve? What are the top five reasons a user with this crisis would not use your product?" The ultimate conclusion of the book is "Figure out what people really want!", which brings to mind the advice to make something people want.
Can Arc be used to create a Tetris-like game? In my previous posting on using OpenGL with Arc, I described how the effort to set up OpenGL had stalled my game-writing adventure. I finally got the game written, only to discover that Conan Dalton had beat me by writing Arc Tetris running on Rainbow, his version of Arc running on Java. Nonetheless, here's my implementation in Arc using OpenGL.
Playing the game
See using OpenGL with Arc for details on setting up OpenGL. To summarize, the files are in the opengl directory of the Anarki git. Run gl-arc.scm in DrScheme. Then load "tet.arc" into the Arc REPL, and the game will start.
To control the game, use the arrow keys. Left and right arrows move the tile. Up-arrow rotates the tile, and down-arrow drops it faster. When the game ends, "s" will start a new game.
Implementing games in Arc
Note that Arc itself doesn't have any graphics support, or any way to get at Scheme libraries. I hacked on Arc's implementation in Scheme to get access to the OpenGL libraries in PLT Scheme.
My first concern with using Arc was speed. It turns out that Arc on a newish laptop is plenty fast to run the game, apart from occasional garbage collection glitches. The game itself doesn't require a fast refresh rate, and the amount of processing per frame is pretty small, so Arc manages just fine.
The biggest problem with implementing the game in Arc was the lack of useful error reporting in Arc; I should have emphasized this in Why Arc is bad for exploratory programming. Every time I wrote more than a few lines at a time, I'd encounter a mystery error such as "ac.scm::18267: car: expects argument of type ; given 1" or "ac.scm::17324: Function call on inappropriate object 2 ()". I often had to stick print statements throughout the code, just to figure out where the error was happening. Reporting what is the error and where an error occurs is basic functionality that a programming language implementation should provide. An actual debugger would be a bonus.
I found that game programming doesn't really let you take advantage of the REPL for development. OpenGL is very stateful, so I can't just call a drawing routine from the REPL to see how it's working. I usually had to restart my code, and often reload the Arc interpreter itself to clear up the various Scheme objects. When I worked incrementally, I often ended up with startup issues when I ran from the start (i.e. variables getting initialized in the wrong order).
One annoyance is Arc's lack of arrays. I used tables in some places, and lists of lists in other places, but vectors and arrays seem like really basic datatypes.
Another annoyance is OpenGL's lack of any text support. If you're wondering about the lack of text in the screenshot, that's why. I implemented a simple 7-segment number-drawing function to display the score.
Some (pretty obvious in retrospect) advice to other game writers: Figure out in advance if the Y axis points up or down. I wrote some of the code assuming Y increases going down before realizing that other parts of the code expected the Y axis to point up. Also, figuring out the origin and scale in advance is a good thing.
Another tricky part of game implementation is state transitions. Both startup and end-of-game caused me more difficulty than I expected.
Implementing the game became much more rewarding once I got a minimal interactive display working. I should have done that sooner, rather than implementing the algorithms up front. On the other hand, I found it useful to disable animation much of the time, using keypresses to single-step movement.
The game has no audio, since PLT Scheme doesn't have audio support.
It took me a long time to realize that the pieces in Tetris don't actually rotate around a fixed point. Once I realized this and hard-coded the rotations instead of implementing a rotation function, things became easier.
I display the piece in motion separately from the playing field array that holds the stationary pieces. When a line is completed, instead of updating the playing field array in place, I decided it would be interesting to write remove-rows in a functional way so it returns an entirely new playing field array, rather than updating the existing array (as I did in saveshape when a piece hits bottom). Writing the whole game in a functional style would be very difficult, as others have described.
I could make the code more "Arcish" with various macros (e.g. w/matrix to wrap code in gl-push-matrix and gl-pop-matrix). But I decided to "ship early". Likewise I didn't bother implementing game levels, although the game does speed up as it progreses. And I've only made minimal efforts to clean up the code, so I'm not presenting it as a model of good style.
Conclusion
It's possible to write a playable game in Arc (with enough hacking on the language to get OpenGL support). I think it would have been considerably easier to write it in PLT Scheme directly, but the Arc implementation builds character. I was pleasantly surprised that Arc had enough speed to run the game. The Arc code works out to 389 lines for those keeping score; OpenGL is responsible for much of the length (50 lines just to display the score). I expect writing in Arc will be considerably easier if the language gets decent error reporting.
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.
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:
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.
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:
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.
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.
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 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:
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":
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:
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.
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.
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:
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.
(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.
(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:
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.
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 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.
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.
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:
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 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.
. It turns out, however, that you can run F# for free in several ways.
.
, a very intersting book about how to think in Scheme. The book uses a unique question-response style to present simple concepts such as 
; trust me, it's all rigorously defined.
. If it's the history of cryptography that interests you, I recommend 
.
