fnargs

W.A.Mozart KV331: Rondo a la Turca, played by Arc

2010-03-01T14:42:00.000-08:00

This midi file was written by arc:

"too many notes, Mozart!"
Emperor Joseph II, on hearing Marriage of Figaro

Musical notation is outrageously repetitive; it seems a ripe candidate for refactoring into a more concise language. Bach had twenty children, and they all had to earn their keep, so he had no shortage of labour for copying out manuscripts, despite which he nonetheless went blind before his death in 1750. So I want to help you make some great music in arc without having to write out zillions of notes all over the place, risking your eyesight in the process. I'm sure you'd like to

  (play:with-feeling moonlight-sonata)
  (play:vigorously mozart-rondo)
  (play:quite-seriously art-of-fugue)

as much as I would. Traditional notation is the assembly language of music, it has been waiting centuries for arc! Step aside, Beethoven; out of my way, Chopin ... s-exps FTW!!1!

Here's what I have so far:

A mini-language for expressing music. ("Language" is a bit of a grandiose term for a ragtag collection of functions and macros)

A converter to convert expressions in this language into midi events.

A writer to write midi events to a midi-format file.

A midi player (rainbow-dependent) that calls a java api to play music.

Only the player depends on rainbow; the rest is vanilla arc.

Rondo a la Turca is low-hanging fruit for this kind of exercise; it's a short piano piece, there is a lot of duplication, which would make for easy compression were it not for the slight variations in each repetition. For example, the second passage consists of

- these are identical except for the hanging half-note at the end of the first version. More insidiously, here are the two variations on the third motif:

It's the same tune, but the first variation specifies a series of notes to be played as octave chords; the second variation specifies the same series of notes, played alternately with their octaves. But I can't express this as a simple transformation; the differences between the passages are not completely consistent.

I'm going to describe how it all works; I'm assuming Dear Reader knows as much about midi as I did when I started, which was approximately nothing, so forgive me if I am mistaken and/or you spot boring bits.

Simple representation

Write arc-music by creating lists of notes. This is what a note looks like:

  (note volume duration . options) ; options specify grace notes, staccato, and other decorations

A chord is a list of notes to be played simultaneously:

  ( (note1 volume duration) (note2 volume duration) )

Music is a sequence of chords.

  ( ((note1 volume1 duration1) (note2 volume2 duration2)) ((note3 vol3 dur3) (note4 vol4 dur4)) etc... )

Single notes are expressed as a chord of one note. Hence, the C Major scale

  (assign c-major-scale
    (mono (c4 mp crotchet) (d4 mp crotchet) (e4 mp crotchet) (f4 mp crotchet)
          (g4 mp crotchet) (a4 mp crotchet) (b4 mp crotchet) (c5 mp crotchet)))

or alternatively,

  (assign c-major-scale
    (apply mono (map [_ mp crotchet] (list c4 d4 e4 f4 g4 a4 b4 c5))))

mono converts a sequence of single notes into a sequence of single-note chords, returning this for c-major-scale:

  (((60 55 16)) ((62 55 16)) ((64 55 16)) ((65 55 16)) ((67 55 16)) ((69 55 16)) ((71 55 16)) ((72 55 16)))

Midi representation

With the above simple representation, the start-time for each note is the sum of all preceding note-durations. Midi doesn't work like this though; it requires note-on and note-off events, each with an explicit time offset, measured in "ticks". To convert from arc-notation to something more closely resembling midi, use make-music:

  (assign music (make-music 0 c-major-scale))

Most music makes ample use of simultaneous notes belonging to different voices; it would be a pain to attempt to express these as chords. Separate voices out this way:

  (assign moonlight (make-music 0 moonlight-sonata-right-hand
                                0 moonlight-sonata-left-hand))

The 0 specifies the midi channel to use, and make-music generates something like

  ( (0 note-on 0 60 64)  (4 note-off 0 60)  (4 note-on 0 62 64)  (8 note-off 0 62)
    (8 note-on 0 64 64) (12 note-off 0 64) (12 note-on 0 65 64) (16 note-off 0 65)
   (16 note-on 0 67 64) (20 note-off 0 67) (20 note-on 0 69 64) (24 note-off 0 69)
   (24 note-on 0 71 64) (28 note-off 0 71) (28 note-on 0 72 64) (32 note-off 0 72))

This list is very close to the structure of an actual midi file, except here I use absolute tick offsets, whereas midi stores delta tick offsets from each event to the next. Items in this list have the following structure:

  (tick-offset event-type channel key velocity)

tick is the offset in ticks from the start of the music when this event should occur; you control the tempo of your music by varying ticks-per-second. Event-type is note-on or note-off (for now; more types coming later); channel specifies the midi channel, so you can play several instruments simultaneously; key corresponds to pitch for most instruments, and velocity to volume (the loudness of a piano keystroke depends on the velocity with which it is struck).

Facing the music

If you're using rainbow, you can pass this list of note-events to play-sequence and actually hear something come out of your speakers.

  (play-sequence (make-music 0 c-major-scale))

You could play more interesting stuff by combining voices:

  (play-sequence (make-music 0 violins-1-part
                             0 violins-2-part
                             1 viola-part
                             2 cello-part
                             3 trombone-part
                             4 trumpet-part
                             5 oboe-part
                             6 flute-1-part
                             6 flute-2-part
                             7 percussion-part))

I haven't tried anything this complex yet. The play-sequence function supports tempo control - I haven't worked that into the midi writer yet.

Depending on your OS and version of java, you may hear music, or something resembling a flatulent wasp. The wasp finally quit my machine after the java update for MacOS in December last year.

The music notation "language"

Having transcribed only two small pieces of keyboard music, I haven't made much language - so far there are only a few simple elements.

Pitch definitions

c1 d1 e1 f1 ... all the way up to f8 g8 a8 b8. Each of these symbols defines a function that creates the corresponding arc-music note.

  (c4 quarter quiet)

returns (60 4 48). Sometimes you need to transform a given starting note, so

  (c4 'transform 2)

returns a function that is identical to d4

The "four-note sequence"

It quickly becomes tedious to write out individual notes, even if they have lovely names. It is the nature of music that small sequences are repeated, perhaps transposed, inverted, or extended. In this example,

four of the six groups of notes are painfully close to being the same thing. Wouldn't it be nice to use a function to create that shape,
taking a pitch and duration parameter? So instead of repeating (mono (c4 mf quaver) (d4 mf quaver) (e4 mf quaver) (f4 mf quaver)), you can write (s2/4/5 c4 mf mf quaver). The 2/4/5 represent the semitone interval count between the first note of the sequence and each subsequent note.

Here are a couple of examples:

	`(s-2/-3/-2 b5 f)`
	`(s1/3/0 f5 f)`

The sX/Y/Z functions are generated from a simple macro invocation. This



  (four-note-sequence
    2  3  5
    2  4 -3
    2  4  0)



generates the functions s/2/3/5,  s/2/4/-3,  s/2/4/0. So it is trivial to extend the vocabulary of this language for other sequences. There is no three-note-sequence macro yet, but Rondo didn't need it. (BWV 147 will, so it's coming)




Volume control



amp transforms the loudness of notes in a sequence. For example ((amp 20) c-major-scale) makes our C Major scale 20 midi-velocity-units louder. loud and quiet are shortcuts for (amp 16) and (amp -16), respectively.



((crescendo 20 8) c-major-scale) transforms the scale by applying a smooth crescendo over the sequence of 8 notes.


An example



The result is pretty ugly. I'm not sure how to improve it; music is at least two-dimensional, code is mostly unidimensional. Compare the musical notation for the opening motif





with the arc version:


  (def rondo-theme (cresc) (+
    (s-2/-3/-2 b4 80)
    (mono (c5 100 2 'staccato) '(pause 2))
    (s-2/-3/-2 d5 80)
    (mono (e5 100 2 'staccato) '(pause 2))
    (s-2/-3/-2 f5 80)
    ((if cresc (crescendo 20 8) idfn) (repeat-list 2 (s-2/-3/-2 b5 80)))
    (mono (c6 (if cresc 120 100) 4))))



Success?



In terms of compression, here are the stats:



rondo.arc: 2586 tokens, 346 lines
rondo-left-hand: 848 items
rondo-right-hand: 1129 items
total: 1977 items, where an item corresponds roughly to a note in a traditional printed score.
rondo-music: 5699 midi events (half of them being 'note-on events, the other half note-off)
resulting midi file, not using any size optimisations: 22864 bytes.




So there are somewhat fewer arc tokens than there are note-on events. It doesn't feel like victory yet though, because s/2/4/5 isn't jumping off the page and ringing bells for me. It's not exactly Emily Howell yet (having a day job and a family is likely to delay progress on that goal). You have ideas for making this better; I'm all ears.


Get the code



I don't know why you'd want to do this: the api is still unstable, and its use is error-prone and frustrating.



















  arc/lib/midi/midi.arc   Collection of functions and macros for declaring music
  arc/lib/midi/rondo.arc   Defines rondo-music, which can subsequently be passed to a midi writer or player
  arc/lib/midi/midi-writer.arc   Defines write-midi-file which outputs your music in midi format (format type 0, the simplest). Supports the bare minimum
      for playing music - note-on and note-off events. No support for any other event type yet.
  arc/rainbow/midi/midi.arc   (rainbow-dependent) Defines play-sequence, which uses a java api to play midi music, and 
      rondo, a convenience function to load dependent libraries and invoke (play-sequence rondo-music)



The fastest way to get this running on your machine is to clone rainbow from github, and run either rainbow or scheme from your working copy.

Playing Rondo from rainbow is as easy as


  (rondo)



Write it to a midi file like this


  (write-midi-to "rondo.midi" rondo-music)



Acknowledgements



Skytopia: Crash course on the standard MIDI specification and

MIDI File Format - The Sonic Spot helped me make sense of the midi format.

The Mutopia project hosts free/open-source PDFs of sheet music, and

LilyPond ... music notation for everyone is the awesome sheet music layout engine that produced the mozart excerpts I've used in this article.

copyright 2008 conan dalton, feel free to quote, please link



Flowers and Spirals and iterated complex functions
2009-07-14T13:41:00.000-07:00
Take a look at spiral.fnargs.com - it's a plotter for the function that generates the Mandelbrot fractal:



  z <- z² + c


These are some of the images it generates:










It's written in arc, using rainbow (in order to access java's image libraries; it could also be done using shell calls to ImageMagick from arc3).


Enjoy.
copyright 2008 conan dalton, feel free to quote, please link


Arc at XP Day France
2009-05-26T12:43:00.000-07:00
Today's arc presentation at XP Day France -

copyright 2008 conan dalton, feel free to quote, please link


Introducing Welder
2009-05-20T12:15:00.000-07:00

When I read Gödel, Escher, Bach, I decided to drop my literature degree and take a computing one instead to learn Lisp. That didn't happen ... I got as far as expertly and elegantly configuring a key binding or two in my ~/.emacs file while struggling with java-mode. Many years later, arc came out, and Paul Graham being who he is, I just had to take a look. Maybe I could build an online ecommerce solution with this stuff, get rich, and turn into an Angel.


Anyway, the first thing I noticed was that I didn't have an editor for arc. Intellij wasn't going to cut the mustard, I wasn't falling in love with Textmate despite those gorgeous RoR screencasts, and I didn't feel like learning DrScheme. And none of these options would give me arc-aware highlighting and evaluation in any case.


So I decided to try what anyone learning a new language should try: write an editor for it. In it. On top of that, I needed something to drive rainbow that would demonstrate easy java integration without polluting the elegance of the arc spirit. And lo, Welder was born. Welder is an arc editor, written in arc. You'll have to forgive, or at least tolerate, the pun. The name "arc" invites it, what else could I do?


Don't get excited - Welder isn't quite ready for prime-time. It's too slow to parse a file (around 5 seconds for arc.arc - 2.5k lines, 13k tokens). The slowness is in the tokeniser, so I'm concentrating my speed-up efforts there. For smaller files (~3k tokens), its performance is tolerable.


These were the minimal required features I started with:



Syntax colouring: strings, numbers, characters, should have their own colours, and symbols should be coloured differently depending on their current bound value, if any. This way it's easy to see if a local variable is shadowing a globally bound symbol, and what kind of a thing it's shadowing.

Paren-matching - highlight matching parentheses, brackets, string delimiters, and any other kind of delimiter that might arise in the future. Also, highlight unbalanced delimiters.

Easy selection of forms: I'm addicted to intellij's "widen selection" - I want to be able to select the entire form enclosing the current expression, in such a way that repeated application selects an increasingly wider scope. This makes copy/paste operations a lot simpler.

Eval: I want to eval the currently selected expression, or the whole file, with a single keystroke

Htmlify: there's no point in writing arc if you're not going to blog about it. But what a pain to reproduce all that syntax highlighting! and besides, if arc gets its herokugarden, this might be a useful part of it.

Configurable keystrokes for all actions

Pretty-printing (doesn't work terribly well)

As well as all the usual editor facilities: undo/redo, cut/copy/paste. Fortunately, java/swing comes with this kind of thing pre-packaged.



Added later:



Font-size control - essential to demo welder on a projector

"pop-form" - replace (foo (bar)) with (bar) if the cursor is on bar

"push-form" - replace x with ( x) - these two together are really useful for inserting/removing a little do, atomic, time, debug or whatever you need for quick refactorings



Note the paren-matching:




And easy form-selection:




Context help for symbol under caret (help text, if present, and the help system, are entirely thanks to the tireless efforts of anarki contributors)




And the complete list of current keybindings:





Welder is still outrageously incomplete. Here are the kinds of thing I would like to add:



Visual macro expander

Common refactorings that are annoying to do by hand - toggle between let and with for example

Navigate to source of symbol declarations

Appropriate highlighting for lexically-bound symbols (I don't know how to do this when the scope is created by a macro, other than macexing everything and working backwards)

Runtime analysis

and everything else ... 



Please suggest and vote for your favourite features!


Welder requires anarki, and is distributed with rainbow on github at http://github.com/conanite/rainbow/tree/master.
copyright 2008 conan dalton, feel free to quote, please link


calling java from arc
2009-01-23T01:43:00.000-08:00
Rainbow adds six builtin functions for calling java code from arc. Theoretically this is all you need to interact with any java library from arc code.



java-new (classname . args)

Create and return a new instance of classname, passing args to the constructor


java-class (classname)

Return a java-object wrapping the class identified by classname


java-invoke (obj method . args)

Invoke method on obj with args. 'defcall binds this function to java-object so that you should only rarely need to call this explicitly. Return the value of the method if there
is any, wrapping into arc types where possible.


java-static-invoke (classname method . args)

Invoke static method on classname with args.


java-static-field (classname fieldname)

Return the value of the specified static field


java-implement (interfacename strictly methods)

Returns a java-object which implements the java interface identified by interfacename, the implementation being provided by the arc code given in methods, where methods is a hash mapping method-name to corresponding implementation. The strictly parameter determines whether an error should be raised if methods does not include all of the methods defined on the interface. java-implement is necessary for implementing, for example, mouse and keyboards handlers for a desktop application, or servlets and filters for a web application.




Following in the arc tradition of using arc-code wrappers for builtin functions (eg 'w/stdout for 'call-w/stdout, 'atomic for 'atomic-invoke, 'thread for 'new-thread), rainbow provides some wrappers to make java interaction a little less ugly and possibly a little more arcish. The 'implement macro removes some boilerplate around 'java-implement, so you can create an implementation of, for example, an iterator (where xs is a list) thus:


(def to-iterator (xs)
  (implement "java.util.Iterator"
    hasNext (fn () xs)
    next    (fn () (pop xs))))


The 'bean function instantiates and configures a java object via its setter methods. Here is an example of creating a JFrame object, specifying its bounds and title:


(def frame (left top width height title)
  (bean "javax.swing.JFrame"
    'bounds       (list left top width height)
    'title        title
    'contentPane  (box 'vertical)))


Behind the scenes, bean is going to call setBounds, setTitle, and setContentPane on a newly-instantiated JFrame object, finally returning the JFrame. 


There are lots more goodies defined in rainbow's swing.arc, but that's a topic for another day.
copyright 2008 conan dalton, feel free to quote, please link


Let There Be Local Variables
2008-06-12T15:07:00.000-07:00
Actually, there aren't any. There are only function parameters. But there's a workaround: use functions.


Suppose you're writing a token analyser for some input. 'token-generator is a generator function. You need to determine the type of a token - return 'string if you think it's a string, 'char, 'int, etc. Naïvely, you might


(def token-type (token-generator)
  (get-token-type (token-generator)))

(def get-token-type (tok)
  (if (is (tok 0 #\")) 'string
      (is (tok 0 #\#) 'char)
      (is-digit (tok 0)) 'int))


So you get your input from 'token-generator, but you're really interested in 'tok. So the function 'get-token-type provides the local variable 'tok for you to work with. The disadvantage is that your namespace gets polluted with a zillion little functions that are only useful to their immediate neighbours. Wouldn't it be nice to, like, click Refactor > Inline Method like you can in a real language?


Well, you can.


(def token-type (token-generator)
  ((fn (tok)
    (if (is (tok 0 #\")) 'string
        (is (tok 0 #\#) 'char)
        (is-digit (tok 0) 'int))) (token-generator)))


The ( (fn (tok) (if blah)) (token-generator) ) is a call to an anonymous function that declares the 'tok parameter for you to work with.


Now your namespace is no longer polluted, but you have this damned ugly thing in the middle of your function. No ordinary human is expected to read this.


Enter 'let


'let is a macro that transforms its humanly-readable input into something resembling the mess above.


(def token-type (token-generator)
  (let tok (token-generator)
    (if (is (tok 0 #\")) 'string
        (is (tok 0 #\#) 'char)
        (is-digit (tok 0) 'int))))


'let lets you pretend you are actually declaring a local variable. Coming from another language, you might think that this is, really and truly, a local variable. It's not. Behind the scenes, it's an anonymous function creating a lexically scoped 'tok parameter. But you don't care. You have your local variable.


Here is the pattern:


(let a b stuff)


becomes:


((fn (a) stuff) b)



'with is a more general purpose macro that does the same thing, but for multiple variables.


(with (a 1 b 2 c 3) stuff)


becomes:


((fn (a b c) stuff) 1 2 3)


'let exists because in the special case of binding just one variable, we don't need parens to separate the variable bindings from the body of the code. Just because you write in lisp doesn't mean you actually like parens ...
copyright 2008 conan dalton, feel free to quote, please link


To Do: If Only ...
2008-06-05T12:21:00.000-07:00
One of the simplest and most pervasive macros in arc is "do". "do" is useful when you need to evaluate a sequence of expressions, but you only have room for one. A common case is when evaluating conditionals:


(if a b
    c d
    e)

This corresponds to the following in java:
if (a) { 
  return b; 
} else if (c) {
  return d;
} else {
  return e;
}


In java, we can execute as many statements as we desire within a { } block; arc however allows only a single expression as return value. So if we wanted


if (a) { 
  b();
  c();
  return d; 
} else if (e) {
  return f;
} else {
  return g;
}


we can't just write


(if a b c d
    e f
    g)


Hence, do.


(if a (do b c d)
    e f
    g)


do expands into a call to a no-arg function containing b c d - 


((fn () b c d))


 - it defines an anonymous zero-arg function and immediately calls it. Hence, b c d are grouped in a single expression, and will work as desired inside a conditional:


(if a ((fn () b c d))
    e f
    g)
copyright 2008 conan dalton, feel free to quote, please link


arc functions
2008-05-29T12:36:00.000-07:00
So the long and the short of it is, we get arc to evaluate expressions. Atoms mostly evaluate to themselves: strings, characters, and numbers. 

arc> "foo"
"foo"
arc> 12
12

Symbols are also atoms, but have the special property that they may be defined to have some other value. Quoting a symbol means it doesn't get evaluated.

arc> 'bar
bar
arc> (set bar "toto")
"toto"
arc> bar
"toto"

Lists are another story: when arc evaluates a list, it assumes the first item of the list is a function, and the remainder are arguments.

arc> (+ 1 2)
3
arc> (expt 9 2)
81

The first item is not necessarily a function: it might also be a reference to a macro, or in anarki, an object for whose type a function has been prepared via defcall. For another day. The first place in a list is usually referred to as "functional position". So, the procedure for evaluating (a b c d), is to evaluate each of a, b, c, and d (order is unspecified). a should evaluate to a function, which is then called with the values of b, c and d as arguments.

But, the object in functional position doesn't have to be a symbol pointing to a function. It could also be an inline, anonymous function.

arc> ((fn (a b) (+ a b)) 23 67)
90

Disadvantage: it's dead ugly, and totally unreadable. Nest a few of these and you have parenthesis soup. It turns out this is one of the fundamental organising principles of arc code. So why bother?
group expressions

declare local variables

iteration

all sorts of wonderful things

 - all this in a neat and concise way, without namespace clutter or parameter hell. Except, we need macros to make it happen. 

Macros: a future post.copyright 2008 conan dalton, feel free to quote, please link


Lexical Scope and Closures
2008-05-22T14:35:00.000-07:00
Lexical scope is not a radical departure from java: the concept already exists. When we create an inner instance class in java, the inner class has access to all the instance variables of all enclosing classes, and even to local variables if it's an anonymous inner class. Similarly, in arc, a locally-defined function has access to all the variables of all enclosing functions. This set of variables and their values is called the closure of the function.



 (def powerfn (y) (fn (x) (expt x y)))
 
 (set square (powerfn 2)) ; --> square is (fn (x) (expt x y)) with y = 2
 (set cube (powerfn 3)) ; --> cube is (fn (x) (expt x y)) with y = 3

 (square 5) ; --> 25
 (cube 5) ; --> 125


In this example, the variable y retains its value - 3 or 2 - long after powerfn has exited, in the closure of the function returned by powerfn (the function that is assigned to square and cube)


When rainbow finds a locally-defined function in the course of evaluation, it creates a Closure object which encapsulates the function in question, and its closure. The Closure thus created can subsequently be stored in a variable, and invoked anywhere at any time. The implementation isn't optimal however: it keeps the entire closure, rather than just the closed variables that are actually used by the function in question.
copyright 2008 conan dalton, feel free to quote, please link


Tail-Call Optimisation
2008-05-15T14:34:00.000-07:00
Tail-Call Optimisation lets you write



public void forever(long n) {
 System.out.println("looking for the last number: " + n)
 if (isTheLastNumber(n)) {
  return;
 }
 forever(n + 1);
}


 - and never get a StackOverflowError. Yes. Never. When a recursive call to forever exits, there is nothing left for the parent invocation of forever to do, so its stack frame can be discarded, and if it is, the stack simply doesn't grow.


Here's an arc example:



(def a ()
 (b)
 (e))

(def b ()
 (c)
 (d))

(def e ()
 (f)
 (g))

(def g ()
 (h)
 (i)
 (j))


Remeber, the return value of a function is the value of the last expression of the function. So the return value of (b) is (d).


After the call from b to (c) returns, execution continues with the call from b to (d). However, when (d) returns, b has nothing more to do, so it can return directly to a.


So, when we call c, we tell it to return to b at Instruction 2. However, when we call d, instead of telling it to return to b, we tell it to return to a. The stack frame representing b at this point is no longer referenced: the continuation for d is pointing back to a, bypassing b altogether.


Ultimately, by the time we get to the call to j, we will tell j to return to whoever a's caller was, because neither a, nor e, nor g, make use of the value of (j). Presumably, a's caller does.


I hope this is making sense.


Here is the implementation in rainbow. Inside the current continuation, the variable f is the function we're evaluating, and f.nth(i) gives us the nth expression of that function. To interpret the nth expression, rainbow does (approximately) this:



   ArcObject expression = f.nth(index++);
   Interpreter.interpret(f.last(index) ? caller : this, expression);


So if I'm on the last expression, I tell the interpreter to return to my caller instead of to me once it's finished. Mission accomplished.


See wikipedia's tail-recursion article for more information. btw, rainbow doesn't do TCO modulo cons (see article). Arc on scheme, it seems, does. I will have to figure that out.
copyright 2008 conan dalton, feel free to quote, please link


Continuations: Arc vs Java
2008-05-08T13:45:00.000-07:00
What's a continuation? Despite much googling on the topic, continuations remained opaque to me until I stumbled upon Sam Ruby's amazingly excellent Continuations for Curmudgeons. Please read that article instead of this, it will be much more useful.


Here's a really fast description of continuations in java terms. Imagine in java we had first-class functions (like javascript). In other words, we could say


Function p = myObject.toString // no parens!

// later ...
p(); // calls myObject.toString()


Now, let's jump a little further: imagine "return" is not just a keyword, but it is a special built-in function that is magically available in the body of every method, just like "this" and "super" are. And we have first-class functions. So, we can write




public String foo(int n) {
  this.cc = return;
  return("foo " + n); // "return" is a function
}


public void bar() {
  System.out.println("I have received " + foo(10));
  System.out.println("end of bar");
}

...

bar(); // displays "I have received foo 10", then "end of bar"
cc("haha!") // displays "I have received haha!", then "end of bar", forever


With the call to cc you are re-entering bar at the instruction immediately after the call to foo(), and not only that, when bar returns, it will return to whoever its caller was when it was invoked the first time, and so on all the way up the stack. Not only that, the stack prior to the call to cc is completely discarded and gc'd (unless, of course, there's a stored continuation somewhere pointing to that stack).


Being a java dude, this was a shocking revelation for me. Worse than goto, a total abomination, a devilish contortion of everything that is right and proper in design.


But I was undeterred. Sam Ruby's article gave me what I needed to implement continuations in rainbow, although it meant re-writing everything. Because java doesn't allow me just store "return", I need to explicitly handle a stack in java code, so that I can "return" to it at any point, just in case someone decides to store it in a continuation. If the stack is stored in this way, it is not subject to garbage collection, so the entire stack - local variables, parameters, the stacktrace - is preserved.


So when rainbow invokes an arc function, it creates a new continuation for the invoked function, and passes the new continuation the current continuation, so the new continuation knows where to return to when it's done.


This results in java code written in Continuation-Passing style, or CPS. CPS and continuations are separate concepts, but feel the same. Here is a quick CPS tutorial in Java. Normally we write this:



 int calculateSomething(int p, int q) {
   return p * q;
 }

 ...

 int x = calculateSomething(p, q);
 System.out.println("result is " + x);


Trivial, no? Here's the same thing in CPS:



 void calculateSomething(int p, int q, Continuation c) {
   c.receive(p * q);
 }

 ... 
 
 Continuation c = new Continuation() {
  public void receive(Object o) {
   System.out.println("result is " + o);
  }
 }

 calculateSomething(p, q, c);


The idea is that your methods must never return a value, they should instead pass the intended return value to a "Continuation" parameter destined to receive it. The responsibility of the Continuation object is to continue whatever was in progress. Here, the Continuation object calls System.out.println, something that was achieved in the second line of the original version. So why would you want to write in CPS? In Java: you wouldn't, it's a nightmare, unless you happen to be writing a Lisp interpreter.


One difference between CPS and true continuations is that a true continuation never returns: the caller's stack is discarded, and the stack in scope for the called continuation is resurrected. CPS in java is a total hack. In the example above, any code following "c.receive(p * q)" is meaningless. The call to receive must be the last statement executed in the method - it's replacing "return". Using CPS in java, it's easy either  to forget to invoke receive, or to forget to return immediately afterwards.


A slight problem for rainbow is that CPS functions never return: the last instruction is a call to the previous continuation. So, normally, the java stack grows and grows. To avoid this, rainbow executes arc in a while(true) loop. Each function invocation simply stores a reference to the function to invoke along with a reference to the caller and the lexical context - and then returns. The java stack unwinds, the loop loops, and the waiting function gets executed.
copyright 2008 conan dalton, feel free to quote, please link


Introducing Rainbow
2008-05-01T23:37:00.000-07:00
Rainbow is an almost full implementation in java of Paul Graham's new lisp, arc. The arc compiler (ac.scm) is written in a little over 1000 lines of scheme - so I figured I could do it in a little over 10000 lines of java. In fact, I got in at about 5000.


Rainbow interprets its internal representation of arc code, and does not compile to bytecode. Hence it is not quite as fast as it might be. Rainbow sports continuations and tail-call-optimisation (which I believe Clojure, the alternative jvm lisp, lacks). These two features, being completely alien to the jvm, perhaps mean that compiling entirely to bytecode will remain out of reach for the moment.


Why java? It's a language I know reasonably well, having used it almost exclusively over the last ten years. Java gives us garbage collection and well-defined thread handling for free, as well as access to some great libraries. On the other hand, java is probably the most politically incorrect language for an arc interpreter: it might cause arc to curl up like a bimetallic strip, a bit like writing a ruby compiler in cobol. What a concept. 


Actually, here's the truth. In Arc at 3 weeks (2001), Paul Graham declares that arc is for good programmers, unlike java, which is for average programmers. I admit it, I am driven by pure hubris.


A goal of arc is to define as much as possible of the language in the language itself. So some keywords that we would expect to be a fundamental part of the language (for example, def and mac, for defining top-level functions and macros) are defined in arc, and not provided by the compiler at all. Rainbow respects this goal and replaces only the scheme compiler while leaving the rest of the language intact.


This blog will be the story of my travels in arc-land, of the challenges faced both in building rainbow and in using arc, from the perspective of someone who has been thinking in java for far too long now ...


Here are the best places to go for more arc info:



Arc - the official site, plenty of background. Be sure to read the tutorial.

the arc forum

arcfn.com - solid and thorough documentation of the language by Ken Shirriff, along with his own experiences integrating arc and opengl

Anarki, the github "unofficial arc" repository, based on Paul Graham's release, with community-contributed features, fixes, and libraries.

Rainbow is also on github
copyright 2008 conan dalton, feel free to quote, please link

arc/lib/midi/midi.arc	Collection of functions and macros for declaring music
arc/lib/midi/rondo.arc	Defines `rondo-music`, which can subsequently be passed to a midi writer or player
arc/lib/midi/midi-writer.arc	Defines `write-midi-file` which outputs your music in midi format (format type 0, the simplest). Supports the bare minimum for playing music - note-on and note-off events. No support for any other event type yet.
arc/rainbow/midi/midi.arc	(rainbow-dependent) Defines `play-sequence`, which uses a java api to play midi music, and `rondo`, a convenience function to load dependent libraries and invoke `(play-sequence rondo-music)`