World's smallest Arc server

The frame below is being served was being served by the Arc language web server running on a SheevaPlug plug computer. (I've replaced the live connection with a screenshot, as I needed to use the SheevaPlug for something else.) Screenshot

The SheevaPlug

SheevaPlug in the wall The SheevaPlug is a compact, inexpensive ($99), low-power (5W), ARM-based Linux server built into a wall-plug. It's fairly powerful despite its size, with an Ethernet port, Flash storage, and a 1.2GHz processor. See plugcomputer.org for more information.

Marvell gave me a SheevaPlug and I thought it would be an interesting platform for experimenting with Arc as a web server. The SheevaPlug seems like a good platform for an always-running web server.

The picture shows the SheevaPlug plugged into the wall, with the Ethernet cable at the bottom. That's not a wall-wart power supply; that's the whole computer.

Since the plug runs Linux, I can just ssh into it and use it like any other Linux server. I installed mzscheme on the SheevaPlug (apt-get install mzscheme), downloaded the Arc language with wget, used iptables to map port 80 to port 8080, and so on. Dynamic DNS provides a DNS name for my SheevaPlug.

Arc

Arc is a new dialect of Lisp, designed by Paul Graham and Robert Morris. It's designed to be compact, flexible, and useful for exploratory programming.

The Arc language now (finally) runs on the current version of mzscheme (link). The ARM version of mzscheme 4.1.3 is easily installable on the SheevaPlug, making it straightforward to run Arc on the SheevaPlug.

The demo is a simple program using the Arc web server. It lets you vote on a set of choices and then graphs the result using a simple HTML/CSS graph. The Arc demo also serves its own source code here.

I'm using Arc on the SheevaPlug mostly to see if it works, since I've been using Arc for a while. For normal SheevaPlug use, you'd probably want to use Apache, PHP, Python, or another normal web server configuration; they all have ARM packages that you can simply install.

I'm just assuming this is the world's smallest Arc server; we'll see if anyone runs Arc on something smaller.

If the server is not working, either I shut it down to do something else or it crashed. Send me email and let me know. You can access the server without the iframe here.

I've also used a Python web server on the SheevaPlug, which is a more mainstream way to go than Arc. In that case, I connected an Arduino to the SheevaPlug, so my Arduino could be accessed over the web.

Admittedly, the demo is just a proof-of concept. The next step is to do something non-trivial with the SheevaPlug and Arc.

Secrets of Arduino PWM

Pulse-width modulation (PWM) can be implemented on the Arduino in several ways. This article explains simple PWM techniques, as well as how to use the PWM registers directly for more control over the duty cycle and frequency. This article focuses on the Arduino Diecimila and Duemilanove models, which use the ATmega168 or ATmega328.

If you're unfamiliar with Pulse Width Modulation, see the tutorial. Briefly, a PWM signal is a digital square wave, where the frequency is constant, but that fraction of the time the signal is on (the duty cycle) can be varied between 0 and 100%.
PWM examples
PWM has several uses:

  • Dimming an LED
  • Providing an analog output; if the digital output is filtered, it will provide an analog voltage between 0% and 100% .
  • Generating audio signals.
  • Providing variable speed control for motors.
  • Generating a modulated signal, for example to drive an infrared LED for a remote control.

Simple Pulse Width Modulation with analogWrite

The Arduino's programming language makes PWM easy to use; simply call analogWrite(pin, dutyCycle), where dutyCycle is a value from 0 to 255, and pin is one of the PWM pins (3, 5, 6, 9, 10, or 11). The analogWrite function provides a simple interface to the hardware PWM, but doesn't provide any control over frequency. (Note that despite the function name, the output is a digital signal.)

Probably 99% of the readers can stop here, and just use analogWrite, but there are other options that provide more flexibility.

Bit-banging Pulse Width Modulation

You can "manually" implement PWM on any pin by repeatedly turning the pin on and off for the desired times. e.g.
void setup()
{
  pinMode(13, OUTPUT);
}

void loop()
{
  digitalWrite(13, HIGH);
  delayMicroseconds(100); // Approximately 10% duty cycle @ 1KHz
  digitalWrite(13, LOW);
  delayMicroseconds(900);
}
This technique has the advantage that it can use any digital output pin. In addition, you have full control the duty cycle and frequency. One major disadvantage is that any interrupts will affect the timing, which can cause considerable jitter unless you disable interrupts. A second disadvantage is you can't leave the output running while the processor does something else. Finally, it's difficult to determine the appropriate constants for a particular duty cycle and frequency unless you either carefully count cycles, or tweak the values while watching an oscilloscope.

Using the ATmega PWM registers directly

The ATmega168P/328P chip has three PWM timers, controlling 6 PWM outputs. By manipulating the chip's timer registers directly, you can obtain more control than the analogWrite function provides.

The AVR ATmega328P datasheet provides a detailed description of the PWM timers, but the datasheet can be difficult to understand, due to the many different control and output modes of the timers. The following attempts to clarify the use of the timers.

The ATmega328P has three timers known as Timer 0, Timer 1, and Timer 2. Each timer has two output compare registers that control the PWM width for the timer's two outputs: when the timer reaches the compare register value, the corresponding output is toggled. The two outputs for each timer will normally have the same frequency, but can have different duty cycles (depending on the respective output compare register).

Each of the timers has a prescaler that generates the timer clock by dividing the system clock by a prescale factor such as 1, 8, 64, 256, or 1024. The Arduino has a system clock of 16MHz and the timer clock frequency will be the system clock frequency divided by the prescale factor. Note that Timer 2 has a different set of prescale values from the other timers.

The timers are complicated by several different modes. The main PWM modes are "Fast PWM" and "Phase-correct PWM", which will be described below. The timer can either run from 0 to 255, or from 0 to a fixed value. (The 16-bit Timer 1 has additional modes to supports timer values up to 16 bits.) Each output can also be inverted.

The timers can also generate interrupts on overflow and/or match against either output compare register, but that's beyond the scope of this article.

Timer Registers

Several registers are used to control each timer. The Timer/Counter Control Registers TCCRnA and TCCRnB hold the main control bits for the timer. (Note that TCCRnA and TCCRnB do not correspond to the outputs A and B.) These registers hold several groups of bits:
  • Waveform Generation Mode bits (WGM): these control the overall mode of the timer. (These bits are split between TCCRnA and TCCRnB.)
  • Clock Select bits (CS): these control the clock prescaler
  • Compare Match Output A Mode bits (COMnA): these enable/disable/invert output A
  • Compare Match Output B Mode bits (COMnB): these enable/disable/invert output B
The Output Compare Registers OCRnA and OCRnB set the levels at which outputs A and B will be affected. When the timer value matches the register value, the corresponding output will be modified as specified by the mode.

The bits are slightly different for each timer, so consult the datasheet for details. Timer 1 is a 16-bit timer and has additional modes. Timer 2 has different prescaler values.

Fast PWM

In the simplest PWM mode, the timer repeatedly counts from 0 to 255. The output turns on when the timer is at 0, and turns off when the timer matches the output compare register. The higher the value in the output compare register, the higher the duty cycle. This mode is known as Fast PWM Mode.
The following diagram shows the outputs for two particular values of OCRnA and OCRnB. Note that both outputs have the same frequency, matching the frequency of a complete timer cycle.
Fast PWM Mode
The following code fragment sets up fast PWM on pins 3 and 11 (Timer 2). To summarize the register settings, setting the waveform generation mode bits WGM to 011 selects fast PWM. Setting the COM2A bits and COM2B bits to 10 provides non-inverted PWM for outputs A and B. Setting the CS bits to 100 sets the prescaler to divide the clock by 64. (Since the bits are different for the different timers, consult the datasheet for the right values.) The output compare registers are arbitrarily set to 180 and 50 to control the PWM duty cycle of outputs A and B. (Of course, you can modify the registers directly instead of using pinMode, but you do need to set the pins to output.)
  pinMode(3, OUTPUT);
  pinMode(11, OUTPUT);
  TCCR2A = _BV(COM2A1) | _BV(COM2B1) | _BV(WGM21) | _BV(WGM20);
  TCCR2B = _BV(CS22);
  OCR2A = 180;
  OCR2B = 50;
On the Arduino Duemilanove, these values yield:
  • Output A frequency: 16 MHz / 64 / 256 = 976.5625Hz
  • Output A duty cycle: (180+1) / 256 = 70.7%
  • Output B frequency: 16 MHz / 64 / 256 = 976.5625Hz
  • Output B duty cycle: (50+1) / 256 = 19.9%

The output frequency is the 16MHz system clock frequency, divided by the prescaler value (64), divided by the 256 cycles it takes for the timer to wrap around. Note that fast PWM holds the output high one cycle longer than the compare register value.

Phase-Correct PWM

The second PWM mode is called phase-correct PWM. In this mode, the timer counts from 0 to 255 and then back down to 0. The output turns off as the timer hits the output compare register value on the way up, and turns back on as the timer hits the output compare register value on the way down. The result is a more symmetrical output. The output frequency will be approximately half of the value for fast PWM mode, because the timer runs both up and down.
Phase-Correct PWM
The following code fragment sets up phase-correct PWM on pins 3 and 11 (Timer 2). The waveform generation mode bits WGM are set to to 001 for phase-correct PWM. The other bits are the same as for fast PWM.
  pinMode(3, OUTPUT);
  pinMode(11, OUTPUT);
  TCCR2A = _BV(COM2A1) | _BV(COM2B1) | _BV(WGM20);
  TCCR2B = _BV(CS22);
  OCR2A = 180;
  OCR2B = 50;
On the Arduino Duemilanove, these values yield:
  • Output A frequency: 16 MHz / 64 / 255 / 2 = 490.196Hz
  • Output A duty cycle: 180 / 255 = 70.6%
  • Output B frequency: 16 MHz / 64 / 255 / 2 = 490.196Hz
  • Output B duty cycle: 50 / 255 = 19.6%

Phase-correct PWM divides the frequency by two compared to fast PWM, because the timer goes both up and down. Somewhat surprisingly, the frequency is divided by 255 instead of 256, and the duty cycle calculations do not add one as for fast PWM. See the explanation below under "Off-by-one".

Varying the timer top limit: fast PWM

Both fast PWM and phase correct PWM have an additional mode that gives control over the output frequency. In this mode, the timer counts from 0 to OCRA (the value of output compare register A), rather than from 0 to 255. This gives much more control over the output frequency than the previous modes. (For even more frequency control, use the 16-bit Timer 1.)

Note that in this mode, only output B can be used for PWM; OCRA cannot be used both as the top value and the PWM compare value. However, there is a special-case mode "Toggle OCnA on Compare Match" that will toggle output A at the end of each cycle, generating a fixed 50% duty cycle and half frequency in this case. The examples will use this mode.

In the following diagram, the timer resets when it matches OCRnA, yielding a faster output frequency for OCnB than in the previous diagrams. Note how OCnA toggles once for each timer reset.
Fast PWM Mode with OCRA top
The following code fragment sets up fast PWM on pins 3 and 11 (Timer 2), using OCR2A as the top value for the timer. The waveform generation mode bits WGM are set to to 111 for fast PWM with OCRA controlling the top limit. The OCR2A top limit is arbitrarily set to 180, and the OCR2B compare register is arbitrarily set to 50. OCR2A's mode is set to "Toggle on Compare Match" by setting the COM2A bits to 01.

  pinMode(3, OUTPUT);
  pinMode(11, OUTPUT);
  TCCR2A = _BV(COM2A0) | _BV(COM2B1) | _BV(WGM21) | _BV(WGM20);
  TCCR2B = _BV(WGM22) | _BV(CS22);
  OCR2A = 180;
  OCR2B = 50;
On the Arduino Duemilanove, these values yield:
  • Output A frequency: 16 MHz / 64 / (180+1) / 2 = 690.6Hz
  • Output A duty cycle: 50%
  • Output B frequency: 16 MHz / 64 / (180+1) = 1381.2Hz
  • Output B duty cycle: (50+1) / (180+1) = 28.2%
Note that in this example, the timer goes from 0 to 180, which takes 181 clock cycles, so the output frequency is divided by 181. Output A has half the frequency of Output B because the Toggle on Compare Match mode toggles Output A once each complete timer cycle.

Varying the timer top limit: phase-correct PWM

Similarly, the timer can be configured in phase-correct PWM mode to reset when it reaches OCRnA.
Phase-Correct PWM with OCRA top
The following code fragment sets up phase-correct PWM on pins 3 and 11 (Timer 2), using OCR2A as the top value for the timer. The waveform generation mode bits WGM are set to to 101 for phase-correct PWM with OCRA controlling the top limit. The OCR2A top limit is arbitrarily set to 180, and the OCR2B compare register is arbitrarily set to 50. OCR2A's mode is set to "Toggle on Compare Match" by setting the COM2A bits to 01.
  pinMode(3, OUTPUT);
  pinMode(11, OUTPUT);
  TCCR2A = _BV(COM2A0) | _BV(COM2B1) | _BV(WGM20);
  TCCR2B = _BV(WGM22) | _BV(CS22);
  OCR2A = 180;
  OCR2B = 50;
On the Arduino Duemilanove, these values yield:
  • Output A frequency: 16 MHz / 64 / 180 / 2 / 2 = 347.2Hz
  • Output A duty cycle: 50%
  • Output B frequency: 16 MHz / 64 / 180 / 2 = 694.4Hz
  • Output B duty cycle: 50 / 180 = 27.8%
Note that in this example, the timer goes from 0 to 180 and back to 0, which takes 360 clock cycles. Thus, everything is divided by 180 or 360, unlike the fast PWM case, which divided everything by 181; see below for details.

Off-by-one

You may have noticed that fast PWM and phase-correct PWM seem to be off-by-one with respect to each other, dividing by 256 versus 255 and adding one in various places. The documentation is a bit opaque here, so I'll explain in a bit of detail.

Suppose the timer is set to fast PWM mode and is set to count up to an OCRnA value of 3. The timer will take on the values 012301230123... Note that there are 4 clock cycles in each timer cycle. Thus, the frequency will be divided by 4, not 3. The duty cycle will be a multiple of 25%, since the output can be high for 0, 1, 2, 3, or 4 cycles out of the four. Likewise, if the timer counts up to 255, there will be 256 clock cycles in each timer cycle, and the duty cycle will be a multiple of 1/256. To summarize, fast PWM divides by N+1 where N is the maximum timer value (either OCRnA or 255).

Now consider phase-correct PWM mode with the timer counting up to an OCRnA value of 3. The timer values will be 012321012321... There are 6 clock cycles in each timer cycle (012321). Thus the frequency will be divided by 6. The duty cycle will be a multiple of 33%, since the output can be high for 0, 2, 4, or 6 of the 6 cycles. Likewise, if the timer counts up to 255 and back down, there will be 510 clock cycles in each timer cycle, and the duty cycle will be a multiple of 1/255. To summarize, phase-correct PWM divides by 2N, where N is the maximum timer value.

The second important timing difference is that fast PWM holds the output high for one cycle longer than the output compare register value. The motivation for this is that for fast PWM counting to 255, the duty cycle can be from 0 to 256 cycles, but the output compare register can only hold a value from 0 to 255. What happens to the missing value? The fast PWM mode keeps the output high for N+1 cycles when the output compare register is set to N so an output compare register value of 255 is 100% duty cycle, but an output compare register value of 0 is not 0% duty cycle but 1/256 duty cycle. This is unlike phase-correct PWM, where a register value of 255 is 100% duty cycle and a value of 0 is a 0% duty cycle.

Timers and the Arduino

The Arduino supports PWM on a subset of its output pins. It may not be immediately obvious which timer controls which output, but the following table will clarify the situation. It gives for each timer output the output pin on the Arduino (i.e. the silkscreened label on the board), the pin on the ATmega chip, and the name and bit of the output port. For instance Timer 0 output OC0A is connected to the Arduino output pin 6; it uses chip pin 12 which is also known as PD6.
Timer outputArduino outputChip pinPin name
OC0A612PD6
OC0B511PD5
OC1A915PB1
OC1B1016PB2
OC2A1117PB3
OC2B35PD3

The Arduino performs some initialization of the timers. The Arduino initializes the prescaler on all three timers to divide the clock by 64. Timer 0 is initialized to Fast PWM, while Timer 1 and Timer 2 is initialized to Phase Correct PWM. See the Arduino source file wiring.c for details.

The Arduino uses Timer 0 internally for the millis() and delay() functions, so be warned that changing the frequency of this timer will cause those functions to be erroneous. Using the PWM outputs is safe if you don't change the frequency, though.

The analogWrite(pin, duty_cycle) function sets the appropriate pin to PWM and sets the appropriate output compare register to duty_cycle (with the special case for duty cycle of 0 on Timer 0). The digitalWrite() function turns off PWM output if called on a timer pin. The relevant code is wiring_analog.c and wiring_digital.c.

If you use analogWrite(5, 0) you get a duty cycle of 0%, even though pin 5's timer (Timer 0) is using fast PWM. How can this be, when a fast PWM value of 0 yields a duty cycle of 1/256 as explained above? The answer is that analogWrite "cheats"; it has special-case code to explicitly turn off the pin when called on Timer 0 with a duty cycle of 0. As a consequency, the duty cycle of 1/256 is unavailable when you use analogWrite on Timer0, and there is a jump in the actual duty cycle between values of 0 and 1.

Some other Arduino models use dfferent AVR processors with similar timers. The Arduino Mega uses the ATmega1280 (datasheet), which has four 16-bit timers with 3 outputs each and two 8-bit timers with 2 outputs each. Only 14 of the PWM outputs are supported by the Arduino Wiring library, however. Some older Arduino models use the ATmega8 (datasheet), which has three timers but only 3 PWM outputs: Timer 0 has no PWM, Timer 1 is 16 bits and has two PWM outputs, and Timer 2 is 8 bits and has one PWM output.

Troubleshooting

It can be tricky to get the PWM outputs to work. Some tips:
  • You need to both enable the pin for output and enable the PWM mode on the pin in order to get any output. I.e. you need to do pinMode() and set the COM bits.
  • The different timers use the control bits and prescaler differently; check the documentation for the appropriate timer.
  • Some combinations of bits that you might expect to work are reserved, which means if you try to use them, they won't work. For example, toggle mode doesn't work with fast PWM to 255, or with output B.
  • Make sure the bits are set the way you think. Bit operations can be tricky, so print out the register values and make sure they are what you expect.
  • Make sure you're using the right output pins. See the table above.
  • You'll probably want a decoupling capacitor to avoid spikes on the output.
An oscilloscope is very handy for debugging PWM if you have access to one. If you don't have one, I recommend using your sound card and a program such as xoscope.

Conclusion

I hope this article helps explain the PWM modes of the Arduino. I found the documentation of the different modes somewhat opaque, and the off-by-one issues unexplained. Please let me know if you encounter any errors.

Arduino + SheevaPlug = Cool Hardware Platform

I recently started using an Arduino in combination with a SheevaPlug as a convenient platform for hardware hacking. The two work together well, with complementary strengths. This describes my experience.

The Arduino

The Arduino is a popular microcontroller platform consisting of a small, inexpensive board and an easy-to-use C-based development environment. The board has multiple digital I/O pins and analog inputs, and a USB serial port connection for programming and communication. The Arduino can be interfaced with a wide variety of hardware. (The Arduino is kind of like a Microchip PIC development board, but uses the ATmega328 AVR microcontroller.) The Arduino is about the size of a credit card (but thick). It has connectors on top which will receive a daughter board (inexplicably called a "shield"), or jumper wires.
The Arduino board
The Arduino is very easy to program and use. The Arduino is programmed using the Wiring language, which is an extension of C with many libraries to interface with various types of hardware. The Arduino IDE provides an editor and compiler for a "sketch" (which is the name for an Arduino program), and downloads the code to the Arduino board over USB. After seeing the Arduino hype at the Maker Faire, I got a Adafruit Arduino Starter Pack, and I've been happy with it. More information about the Arduino is at www.arduino.cc; the playground is a good place to start.

You can do a lot with an Arduino, but it has some limitations. There's only 30KB of memory for programming (yes, kilobytes). Many things you might want to connect (Ethernet, SD card, USB hard drive or flash) require additional hardware, and even then are pretty limited.

The SheevaPlug

The Marvell SheevaPlug is a very small Linux server with a 1.2GHz 88F6281 ARM processor and 512MB of RAM and 512MB of flash storage. The SheevaPlug has a Gigabit Ethernet connection, a SD card slot, and a serial USB console connection. This all fits into a box the size of three cassette tapes that sells for $99 and uses about 5 watts of power.
The SheevaPlug
The SheevaPlug is designed to be plugged directly into the wall as a wall-wart, but the plug snaps out and can be replaced by a power coard. I'm currently using the "desktop" configuration with a power cord, since it's easier to connect things. Marvell recently gave me a SheevaPlug, and I've been enjoying it a lot.

Because the SheevaPlug is a full Linux system, the standard Linux software packages are available and easily installed with apt-get (full list). You can run X-windows (of course you need to VPN in). You can run Apache and PHP on the SheevaPlug and use it as a web server. The GCC toolchain runs on it. You can program it in C++, Python, Scheme, or whatever.

The main information source on the SheevaPlug is plugcomputer.org. Another useful site is computingplugs.com, a wiki about the SheevaPlug which is actually served by a SheevaPlug.

There are a few limitations of the SheevaPlug. The SheevaPlug is headless, so you need to access it via ssh or VNC. You can't run x86 binaries. The SheevaPlug's performance is roughly at the Pentium III level (benchmark), so it won't replace a state-of the-art server. Also, floating point performance is poor since there's no hardware FPU. The Linux install has some annoying minor issues with apt-get, DNS, NTP, and passwd (fixes). The SheevaPlug isn't really suited for low-level electronics projects because it doesn't have any accessible general-purpose I/O pins. (The CPU has 50 digital GPIO pins, but the SheevaPlug doesn't expose them.)

Arduino + SheevaPlug

The SheevaPlug and Arduino make a great pair together for hardware hacking projects since the SheevaPlug can easily provide the web server, computing, and storage functionality that the Arduino lacks, while the Arduino makes it easy to interface to hardware circuits. Moreover, the two are easily connected with a USB cable, and then they can communicate through simple serial communication (modulo kernel details below).
SheevaPlug with Arduino
The above picture shows the SheevaPlug and Arduino connected together by a USB cable. The SheevaPlug also has an Ethernet connection (green) and power (on the right). The Arduino has some jumpers to a breadboard circuit (described below).

A sample project: illumination recording

For an initial project, I decided to collect data on the illumnination in my room. (Temperature would have been more useful, but I didn't have a temperature sensor handy.) I implemented a simple Arduino sketch (i.e. program) to read illumination from a photocell and write it to the serial port. The SheevaPlug collects the data, generates a graph using gnuplot, and provides the data as a web page on the Internet. (Sorry, no URL to access it since I'm not currently running this.)

The screenshot below shows the web page that the SheevaPlug serves showing illumination across a few days. There are a lot of spikes due to turning lights on and off, but you can see where the sun rises, light increases through the day, peaking shortly before sunset. This web page illustrates the ability of the Arduino to measure analog data combined with the SheevaPlug's ability to collect data, plot it, and serve web pages.
SheevaPlug screenshot of browser

The Arduino code

Hooking up the Arduino to measure illumination was trivial; I used a 10K resistor and a photocell connected to an analog input pin. (I made the following schematic with Eagle.)
schematic of photocell connection

The Arduino sketch below (download) simply reads the analog input once a second and writes the value to the serial port as a decimal number. (One annoyance is the Arduino IDE won't run on the ARM processor, so I have to connect the Arduino to a separate computer to download the sketch.)

int ainPin = 2;     // select the analog input pin

void setup() {
  Serial.begin(9600);
}

void loop() {
  Serial.println(analogRead(ainPin), DEC);    // read the value from the sensor and write to serial
  delay(1000);
}

The Python code

The Python code that runs on the SheevaPlug (download) is straightforward. I used a simple Python web server to provide the graph page and some static files. It uses gnuplot to generate the graph. Some highlights of the code:

The pyserial library (apt-get install python-serial) provides simple access to the serial port. One thread reads lines from the serial port and dumps them to the data file along with a timestamp. Only one sample per minute is kept, and the others discarded. The Arduino may appear as a different device, e.g. /dev/ttyUSB0. If no such device appears when you plug the Arduino into the SheevaPlug, you probably need the kernel update below.

class Arduino(threading.Thread):
  def run(self):
    f = open('/tmp/data', 'a')
    # Port may vary from /dev/ttyUSB1
    self.ser = serial.Serial('/dev/ttyUSB1', 9600, timeout=10)
    self.ser.flushInput()
    old_timestamp = None
    while 1:
      data = self.ser.readline().strip()
      if data:
        timestamp = time.strftime("%m/%d/%Y %H:%M", time.localtime())
        if timestamp != old_timestamp:
          # Only log once per minute
          print >>f, timestamp, data.strip()
          old_timestamp = timestamp
        f.flush()

The other part of the Python code is an HTTP server using SimpleHTTPServer; a /graph URL runs gnuplot on the data file to generate a png image file. The returned web page loads the image, which is served by the Python server as a static file. (Since the SheevaPlug supports Apache, PHP, and mysql, I could have used them, but it seems like overkill for a simple demo.)

 def graph(self):
    g = os.popen('gnuplot', 'w')
    print >>g, GNUPLOT_CMD
    self.send_response(200)
    self.send_header('Content-type', 'text/html')
    self.end_headers()
    self.wfile.write(GRAPH_HTML)

Kernel with FTDI Serial support

The one stumbling block I encountered when using the SheevaPlug and Arduino together is the SheevaPlug kernel doesn't include FTDI support, which is necessary to access the Arduino via USB. An upgraded kernel is available, and much to my surprise it installed with no problems.

Where from here?

So far, I've found the Arduino and SheevaPlug to work together well. I have various plans to use the Arduino + SheevaPlug for home monitoring and control, solar panel monitoring, IR remote control, and other random projects. If there's interest, maybe I'll write about them in the future.

Inside the news.yc ranking formula

The recent arc3 release of Arc includes news.arc, the Arc source code for the Hacker News forum. Examining this code can give some insight into the ranking algorithm that selects the top articles on the Hacker News forum.

The ranking formula

In outline, each item is given a ranking, and the articles are sorted according to the ranking. The simplistic way to think about ranking is the number of votes is divided by time, so more votes results in a higher ranking, but the ranking also drops over time. The votes are raised to a power less than one, while the time is raised to a power greater than one, so time has more effect than votes. Some additional penalties also may be applied to the ranking.

To be specific, the following is the ranking code from news.arc:

(= gravity* 1.8 timebase* 120 front-threshold* 1
   nourl-factor* .4 lightweight-factor* .3 )

(def frontpage-rank (s (o scorefn realscore) (o gravity gravity*))
  (* (/ (let base (- (scorefn s) 1)
          (if (> base 0) (expt base .8) base))
        (expt (/ (+ (item-age s) timebase*) 60) gravity))
     (if (no (in s!type 'story 'poll))  1
         (blank s!url)                  nourl-factor*
         (lightweight s)                (min lightweight-factor*
                                             (contro-factor s))
                                        (contro-factor s))))

This algorithm can be expressed as a (slightly simplified) equation:

rank=\frac{ \left( score-1 \right) ^{.8}}{ \left( age _{hours} + 2 \right) ^ {1.8}} * penalties

This ranking algorithm is used for items on the front page as well as for ordering the comments on an item.

The key factor in the ranking formula is the exponent on time (i.e. the optional parameter gravity) is higher than the exponent on the votes. As a result, even if an item keeps getting a large number of votes, eventually the denominator will overwhelm it and its ranking will drop. For example, if a popular item gets 100 votes an hour, eventually it won't be able to keep pace with a new item getting 10 votes an hour. This ensures that even the most popular items won't stay on the list forever. In other words, gravity controls how fast articles get pulled down in ranking.

By default, the scoring function scorefn is the realscore, which is the net votes for an item ignoring any upvotes from pontential sockpuppet accounts. Sockpuppet accounts are accounts created to manipulate voting, and an account is considered potentially a sockpuppet based on several simple factors.

Because the score is given an exponent of .8 (for positive scores), the benefit of large numbers of votes is reduced. Mathematically, though, this exponent could be eliminated. Since only relative rankings matter, raise everything to the 1/.8 power, and the numerator's exponent disappears, along with the need for the negative check. This would be a win from the "code golf" perspective.

A few other constants are of interest. Since 1 is subtracted from the score, an item starts off with a rank of 0. In the denominator, 120 minutes are added to the time. Thus, an article can be considered two hours old at time of posting, limiting the ranking boost for very recent articles. The front-threshold* specifies a minimum ranking score for articles to appear.

Penalties

A story (i.e. a normal posting) or poll can receive additional ranking penalties. The penalties are not applied to comments or poll options. The penalties are as follows:
  • An item with a blank url is penalized by nourl-factor*. This lowers the ranking of an "Ask HN" item, for instance.
  • A "lightweight" item is penalized.
  • A "controversial" item is penalized.
An item is considered lightweight if the title is a "rallying cry", the post is an image, or the URL's site is in a list of lightweight sites. A lightweight item is penalized by lightweight-factor*. (The code doesn't show how a "rallying cry" is determined.)

The contro-factor penalty is applied to controversial articles. The contro-factor is computed as:

(def contro-factor (s)
  (aif (check (visible-family nil s) [> _ 20])
       (min 1 (expt (/ (realscore s) it) 2))
       1))
An item with too many comments (at least 20 and more comments than upvotes) gets the contro-factor penalty. An item's visible-family is the number of visible comments (plus one for the item itself). If the visible-family is more than 20, the penalty is:

min\left[ 1, \left( \frac{realscore}{visible\-family}\right) ^{2} \right]

A lightweight item gets the worse of the "lightweight" and "contro-factor" penalties. The contro-factor penalty is only applied if less than 1; i.e. an item can't get a boost from it. Because the ratio is squared, the effect of the penalty is more substantial. I would have expected contro-factor to penalize controversial comment subthreads too, but apparently it doesn't.

How the ranking is performed

When the server starts up, it loads the top stories from a topstories file. If the file is not present, it uses the ranking algorithm to select the top 180 stories out of the most recent 1000 stories. Stories normally are re-ranked by adjust-rank only when they receive a vote. Interestingly, only the updated item is re-ranked, rather than doing a global re-rank, probably for efficiency reasons. The adjust-rank function also saves the top 180 items to thetopstories file to disk.

There's also a background reranking thread to rerank a random story from the top 50 every 30 seconds (again using adjust-rank). This ensures that stories that are no longer receiving any votes at all get reranked occasionally.

As far as I can tell, the list of ranked stories never gets shrunk (except on restarts), but the number of displayed stories is capped at 210; you will hit this limit if you keep paging through the top stories.

Comparison with Arc2

The old code in arc2 is much simpler:
(= gravity* 1.4 timebase* 120 front-threshold* 1)

(def frontpage-rank (s (o gravity gravity*))
  (/ (- (realscore s) 1)
     (expt (/ (+ (item-age s) timebase*) 60) gravity)))
The main differences are that arc3 has higher gravity, so articles will drop off faster; arc3 has an exponent on the numerator, and arc3 adds the various penalties. This illustrates that the ranking formula is changing and gaining complexity over time.

Conclusions

There may be differences there are between the live Hacker News server and news.arc, so my analysis may not exactly describe what's really happening. I'd assume the code is constantly being modified; comparison with arc2 shows that the ranking formula has become considerably more complex. In addition, news.arc has some YC-specific stuff removed.. Finally, since this is Arc, the ranking constants and even the algorithms can be changed at the REPL while the server is running. Thus, the live ranking algorithm might never actually exist in a source file.

So, what's the secret to getting a high-ranked article? I don't see any magic bullets in the code, just the obvious: get lots of upvotes in a short period of time, avoid penalties (don't post fluff), and don't use sockpuppets.

What's new in arc3?

The long-awaited new update of Arc (arc3) has been made available. I've examined the release to determine what's new in arc3 beyond the mysterious new logo: arc logo.

arc3 is a major change from arc2, with about 3000 lines and most files changed. The following gratuitous pie chart illustrates that the largest number of changes are in the news server (news.arc), with many changes to the fundamental language (ac.scm and arc.arc) as well as the web and application servers (app.arc and srv.arc).
Summary of changes
The news server has been heavily modified with new ranking, support for polls, and improved spam rejection, among other features. A new "how-to-run-news" file explains how to set up your own Hacker News-like server. I will discuss the news server, web server, app server, and html library in more detail in a future article. I will focus this article on the language and main libraries.

If you're looking to try arc3, it can be downloaded here. Arc3 has significant incompatibilities with previous versions that will cause problems if you're not prepared.

Incompatibilities

  • Arc now requires mzscheme 372. Arc will not work with the version 352 required by arc2, or with the newer versions of mzscheme.
  • flush-output is disabled by default on write, disp, and functions that use these. See declare below.
  • The result of accum is no longer in reverse order.
  • news.arc is no longer loaded as part of arc.
  • a.b.c is now ((a b) c), not (a b c)
  • a!b!c is now ((a 'b) 'c), not (a 'b 'c)
  • The set function has been renamed assign, and the assert function has been renamed set.
  • writefile1 removed.
  • flat no longer supports stringstoo option.
  • to-nearest renamed to nearest.
  • random-elt renamed to rand-elt.
  • firstn-that renamed to retrieve.
  • plural renamed to pluralize.

New functions

  • int function coerces to an integer.
  • force-close discards buffered output and closes the descriptor.
  • mvfile moves a file.
  • memory returns the current memory use.
  • sin, cos, tan, and log are finally available.
  • declare is used to set system variables: explicit-flush to control automatic output flushing, and direct-calls for the function call optimization.
  • timedate converts seconds to date.
  • copylist copies a list.
  • defs applies def to name, args, body triples to define multiple functions at once.
  • get provides simpler table / array lookup. get!foo creates a function that takes a table and looks up 'foo. (Actually, it's a generic mechanism to create a function to apply an argument to something.)
  • writefile writes to a temporary file first.
  • letter tests if a character is a letter.
  • sum sums up function results.
  • med returns median of list.
  • minutes-since returns minutes since a time.
  • defcache wrapper around cache to reduce boilerplate.
  • datestring creates "y - m - d" string.
  • or= modifies a variable if the variable is false.
  • out evaluates and prints an expression.
  • fromdisk, diskvar, disktable, and todisk provide a simplified mechanism for loading and storing data.
  • halve splits a string in two on the first separator.
  • positions returns a list of positions where a test is true.
  • lines splits a string into lines.
  • urlencode urlencodes a string.
  • nonblank returns a string if it's nonblank.
  • plural returns a count and pluralized word.

Bug fixes

  • atomic-invoke fixed.
  • socket-accept uses custodians so web servers can forcibly close connections if the clients aren't reading data.
  • coerce of string into int rounds the value as does number to char.
  • list modified to copy the list.
  • safeset now writes warnings to stderr.
  • each fixed to avoid conflict with afn.
  • cut fixed.
  • trues fixed.
  • whiler fixed.
  • rand-string now more random to help fix huge security hole.
  • split fixed for negative positions..
  • memo now memoizes nil results too.
  • readline will terminate on nil.
  • copy fixed.
  • hours-since fixed.
  • date fixed to avoid system operation.
  • intersperse now works with nil.
  • load fixed.
  • posmatch fixed.
  • num fixed to handle negative numbers.

Optimizations

  • complement in function position
  • The <, >, and + operations when applied to two arguments.
  • (foo bar) is optimized to call foo directly if foo is a global bound to a function. This is controlled by declare.

Other changes

  • Debugging has been improved by giving the Arc names of things to Scheme, and turning on line counting.
  • A default value can be provided when accessing a hash table.
  • Currying was largely implemented but not enabled.
In conclusion, arc3 has some nice improvements, bug fixes, and optimizations, but nothing too dramatic in the language itself. If you're using the Arc news server, you'll definitely want arc3 for the security fixes. On the other hand, the unofficial Anarki release of Arc has a lot of interesting features too.

Disclaimers: I have provided my interpretations of the changes in arc3, and I'm sure there are some errors; please provide feedback if you find mistakes. Note that I am not connected with the arc team in any way, and this is not an "official" list of changes. In addition, arc3 may change without warning, so any of the above can be obsoleted. (There are some good reasons for real version numbers, bug tracking, and source code control, but I won't belabor that point.)

Arc errors (slightly) demystified

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> )
Error: "UNKNOWN::910: read: unexpected ')'"

arc> (def foo (x) (prn x))
#<procedure: foo>
arc> (foo 1 2)
Error: "procedure  foo: expects 1 argument, given 2: 1 2"
This error message is straightforward - too many arguments were given to the procedure..
arc> (def (bar (x) (prn x)))
Error: "#<procedure>: expects at least 2 arguments, given 1: (bar (x . nil) (prn x . nil) . nil)"
In this case, the expected arguments error is more mysterious. Misplaced parentheses generate this error from the depths of the interpreter.
arc> (+ 1 ("s"))
Error: "car: expects argument of type <pair>; given ()"
You probably have extra parentheses, attempting to index into a string. For a number, the error message is much clearer:
arc> (+ 1 (42))
Error: "Function call on inappropriate object 42 ()"

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.

F# for Cheapskates

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.)

  • Download Visual Studio 2008 Shell SP1 (integrated mode).
  • 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.
  • Download and install F# 2009 CTP (msi).

Running F# inside Visual Studio Shell

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.

F# in Visual Studio

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.

F# in Visual Studio

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# under mono

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!

Why Unicode is important

A couple months ago I went to a French cafe at the Denver airport. Outside the restaurant was a large rotating menu, clearly costly to manufacture. Some of the beverages on the menu puzzled me: "Caf  Latte", "Caf  Americano", and "Caf  Mocha".
faulty menu
When I saw "Proven al Salad", I realized that they had suffered an unfortunate accented character mishap; the menu was supposed to offer "Café Latte", "Café Americano", "Café Mocha", and "Provençal Salad". Unfortunately, the accented characters disappeared somewhere in the sign printing process. The font, likely Marker Felt Thin, has accented characters, so they should have been able to get it right.

I {entity} unicode So... can any deep insight be extracted from this, or is it just a somewhat entertaining picture? My first conclusion is that notwithstanding the Arc Unicode debacle, support for non-ASCII characters is important even if you're a sign shop in Denver. My second conclusion (based on personal experience) is that everything conspires to destroy non-ASCII characters, and it's non-trivial to get them right. My third conclusion - which will make sense if you've seen UTF-8 get misinterpreted as latin-1 - is the restaurant should be grateful that they didn't end up with "Café Latte".

The Y Combinator in Arc and Java

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:
arc> ((fact-gen nil) 0)
1
arc> ((fact-gen nil) 1)
Error: "Function call on inappropriate object nil (0)"
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:
arc> ((fact-gen (fact-gen (fact-gen (fact-gen (fact-gen nil))))) 4)
24
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:
(def Y (r)
  ((fn (f) (f f))
   (fn (f)
     (r (fn (x) ((f f) x))))))
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:

arc> (((fn (r)
  ((fn (f) (f f))
   (fn (f)
     (r (fn (x) ((f f) x))))))

(fn (fact)
 (fn (n)
  (if (is n 0) 1
      (* n (fact (- n 1)))))))

10)
3628800
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.(f f)) λf.(r λx.((f f) 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:

Readline support for Arc

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.

Simple Cryptanalysis with Arc

I came across a thread on reddit about why you shouldn't write your own encryption algorithm. In it, one person presented a homegrown algorithm with a challenge to break it. The algorithm turned out to be the weak Vigenère cipher, so I thought it would be interesting to break it with Arc.

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:
(for i 1 20 (prn i " " (autocorrelate s i)))
1 2
2 3
3 1
4 6
5 6
6 16
7 6
8 3
9 0
10 1
11 3
12 16
13 7
14 5
15 0
16 3
17 5
18 17
19 1
20 3
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:
(def testall (s startpos skip)
  (for i 0 (len m)
    (pr i " ")
    (decodesubstring s startpos skip i)))

(testall s 2 6)
0 GRxswKx";wEsMHLLsxLsxzHsMsNstsMMxAAztM
1 FQwrvJw~"vDrLGKKrwKrwyGrLrMrsrLLwzzysL
2 EPvquIv=~uCqKFJJqvJqvxFqKqLqrqKKvyyxrK
3 DOuptHu+=tBpJEIIpuIpuwEpJpKpqpJJuxxwqJ
4 CNtosGt)+sAoIDHHotHotvDoIoJopoIItwwvpI
5 BMsnrFs()rznHCGGnsGnsuCnHnInonHHsvvuoH
6 ALrmqEr*(qymGBFFmrFmrtBmGmHmnmGGruutnG
7 zKqlpDq^*pxlFAEElqElqsAlFlGlmlFFqttsmF
8 yJpkoCp%^owkEzDDkpDkprzkEkFklkEEpssrlE
9 xIojnBo$%nvjDyCCjoCjoqyjDjEjkjDDorrqkD
10 wHnimAn#$muiCxBBinBinpxiCiDijiCCnqqpjC
11 vGmhlzm@#lthBwAAhmAhmowhBhChihBBmppoiB
12 uFlgkyl!@ksgAvzzglzglnvgAgBghgAAloonhA
13 tEkfjxk\!jrfzuyyfkyfkmufzfAfgfzzknnmgz
14 sDjeiwj/\iqeytxxejxejlteyezefeyyjmmlfy
15 rCidhvi?/hpdxswwdiwdiksdxdydedxxillkex
16 qBhcguh'?gocwrvvchvchjrcwcxcdcwwhkkjdw
17 pAgbftg-'fnbvquubgubgiqbvbwbcbvvgjjicv
18 ozfaesf,-emaupttaftafhpauavabauufiihbu
19 nye dre.,dl toss es ego t u a ttehhgat
20 mxd;cqd9.ck;snrr;dr;dfn;s;t; ;ssdggf s
21 lwc"bpc89bj"rmqq"cq"cem"r"s";"rrcffe;r
22 kvb~aob78ai~qlpp~bp~bdl~q~r~"~qqbeed"q
23 jua= na67 h=pkoo=ao=ack=p=q=~=ppaddc~p
24 it +;m 56;g+ojnn+ n+ bj+o+p+=+oo ccb=o
25 hs;)"l;45"f)nimm);m);ai)n)o)+)nn;bba+n
26 gr"(~k"34~e(mhll("l(" h(m(n()(mm"aa )m
27 fq~*=j~23=d*lgkk*~k*~;g*l*m*(*ll~  ;(l
28 ep=^+i=12+c^kfjj^=j^="f^k^l^*^kk=;;"*k
29 do+%)h+01)b%jeii%+i%+~e%j%k%^%jj+""~^j
30 cn)$(g)Z0(a$idhh$)h$)=d$i$j$%$ii)~~=%i
31 bm(#*f(YZ* #hcgg#(g#(+c#h#i#$#hh(==+$h
32 al*@^e*XY^;@gbff@*f@*)b@g@h@#@gg*++)#g
33  k^!%d^WX%"!faee!^e!^(a!f!g!@!ff^))(@f
34 ;j%\$c%VW$~\e dd\%d\%* \e\f\!\ee%((*!e
35 "i$/#b$UV#=/d;cc/$c/$^;/d/e/\/dd$**^\d
36 ~h#?@a#TU@+?c"bb?#b?#%"?c?d?/?cc#^^%/c
37 =g@'! @ST!)'b~aa'@a'@$~'b'c'?'bb@%%$?b
38 +f!-\;!RS\(-a=  -! -!#=-a-b-'-aa!$$#'a
39 )e\,/"\QR/*, +;;,\;,\@+, ,a,-,  \##@-
40 (d/.?~/PQ?^.;)""./"./!).;. .,.;;/@@!,;
41 *c?9'=?OP'%9"(~~9?~9?\(9"9;9.9""?!!\."
42 ^b'8-+'NO-$8~*==8'=8'/*8~8"898~~'\\/9~
43 %a-7,)-MN,#7=^++7-+7-?^7=7~787==-//?8=
44 $ ,6.(,LM.@6+%))6,)6,'%6+6=676++,??'7+
45 #;.59*.KL9!5)$((5.(5.-$5)5+565)).''-6)
46 @"948^9JK8\4(#**49*49,#4(4)454((9--,5(
47 !~837%8IJ7/3*@^^38^38.@3*3(343**8,,.4*
48 \=726$7HI6?2^!%%27%279!2^2*232^^7..93^
49 /+615#6GH5'1%\$$16$168\1%1^121%%69982%
50 ?)504@5FG4-0$/##05#057/0$0%010$$58871$
51 '(4Z3!4EF3,Z#?@@Z4@Z46?Z#Z$Z0Z##47760#
52 -*3Y2\3DE2.Y@'!!Y3!Y35'Y@Y#YZY@@3665Z@
53 ,^2X1/2CD19X!-\\X2\X24-X!X@XYX!!2554Y!
54 .%1W0?1BC08W\,//W1/W13,W\W!WXW\\1443X\
55 9$0VZ'0ABZ7V/.??V0?V02.V/V\VWV//0332W/
56 8#ZUY-ZzAY6U?9''UZ'UZ19U?U/UVU??Z221V?
57 7@YTX,YyzX5T'8--TY-TY08T'T?TUT''Y110U'
58 6!XSW.XxyW4S-7,,SX,SXZ7S-S'STS--X00ZT-
59 5\WRV9WwxV3R,6..RW.RWY6R,R-RSR,,WZZYS,
60 4/VQU8VvwU2Q.599QV9QVX5Q.Q,QRQ..VYYXR.
61 3?UPT7UuvT1P9488PU8PUW4P9P.PQP99UXXWQ9
62 2'TOS6TtuS0O8377OT7OTV3O8O9OPO88TWWVP8
63 1-SNR5SstRZN7266NS6NSU2N7N8NON77SVVUO7
64 0,RMQ4RrsQYM6155MR5MRT1M6M7MNM66RUUTN6
65 Z.QLP3QqrPXL5044LQ4LQS0L5L6LML55QTTSM5
66 Y9PKO2PpqOWK4Z33KP3KPRZK4K5KLK44PSSRL4
67 X8OJN1OopNVJ3Y22JO2JOQYJ3J4JKJ33ORRQK3
68 W7NIM0NnoMUI2X11IN1INPXI2I3IJI22NQQPJ2
69 V6MHLZMmnLTH1W00HM0HMOWH1H2HIH11MPPOI1
70 U5LGKYLlmKSG0VZZGLZGLNVG0G1GHG00LOONH0
71 T4KFJXKklJRFZUYYFKYFKMUFZF0FGFZZKNNMGZ
72 S3JEIWJjkIQEYTXXEJXEJLTEYEZEFEYYJMMLFY
73 R2IDHVIijHPDXSWWDIWDIKSDXDYDEDXXILLKEX
74 Q1HCGUHhiGOCWRVVCHVCHJRCWCXCDCWWHKKJDW
75 P0GBFTGghFNBVQUUBGUBGIQBVBWBCBVVGJJICV
76 OZFAESFfgEMAUPTTAFTAFHPAUAVABAUUFIIHBU
77 NYEzDREefDLzTOSSzESzEGOzTzUzAzTTEHHGAT
78 MXDyCQDdeCKySNRRyDRyDFNySyTyzySSDGGFzS
79 LWCxBPCcdBJxRMQQxCQxCEMxRxSxyxRRCFFEyR
80 KVBwAOBbcAIwQLPPwBPwBDLwQwRwxwQQBEEDxQ
81 JUAvzNAabzHvPKOOvAOvACKvPvQvwvPPADDCwP
82 ITzuyMz ayGuOJNNuzNuzBJuOuPuvuOOzCCBvO
83 HSytxLy; xFtNIMMtyMtyAItNtOtutNNyBBAuN
84 GRxswKx";wEsMHLLsxLsxzHsMsNstsMMxAAztM
85 FQwrvJw~"vDrLGKKrwKrwyGrLrMrsrLLwzzysL
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:

(= s2 "sBC^myM3f5MC6nBF~d?OM*mqt5y@wB3Bvt'm6vy%vIB3x9RNJmJB@y,Bt6rHN4m@FS3nrF8d(It5rpL8e8:t^BpN,e(tw,AuO?m^wB8ApG4C4Ny^GpI(x4NB-Fpy!g^SJ*vEH3q9NB@q+t3M.tB8mIO6g9yx^mpQ8p\\tx@Auf3dhtM-Asy%i\\St6BDA%e(OF4Gut,m!;t3Vvt,i4xI8FpH@x4t23nIE3x-uN3nJt/i5MN3uut!s(tw@AJC!y9tN@mCu?i4zO!mEz3x-CM3pyJ,i^tQ,vsB3m*tM@muu^C4ut1$pS8e^tI/qnt6s)Fx3pHu6o4CNJmEL3b'Nt6nDt5i4wL4pAy7d6St,nDx1d5ww@EtC!k4NI3BJB8v*;t3YuN3q9tL8Cuu*d#Hw8mCI%i4t23xDI+d'NtaN3t5i4wL4pAy7/4vO*mYt5i(t6m59t#i#JF8miL8h8CN3vIt!s(tr\\BIN3t9IJ/rnn3A#Hb*mtI3m(;")
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.

QR codes in Lego

I've been experimenting with QR codes (2-d bar codes) with my mobile phone. While helping my daughter assemble a Lego® spaceship, I had the random thought that maybe I could build a QR code out of Lego. Would such a QR code be readable, or would the bumps and gaps mess it up?

To find out, I generated a QR code and started assembling it out of my daughter's spare Lego pieces. This would have been much easier if she had a lot of small white pieces, so I needed to really dig to find the necessary 1x1 blocks. (I'm pretty sure that determining if a code can be tiled with a specific set of blocks is a NP-complete problem, but my manual heuristics were sufficient to get it assembled.)

The moment of truth... would it scan? No, not at all. The problem was I needed a border around the code block and I'd put the pieces too close to the edge. So I laboriously shifted all the pieces over and added a white border.

Lego QR code

With the border, the QR code scanned amazingly well. Here's a camera-eye view. If you have a barcode-enabled phone, you can probably scan this off the screen:

Lego QR code

I used the ZXing barcode scanning program on my phone. I expected the scan would be sensitive to the orientation, lighting, and distance, since Lego isn't very even. However, the phone scanned the blocks surprisingly rapidly and effectively. Note the orientation-independence:

Phone scanning Lego QR code

My conclusion is that Lego is a viable medium for implementing QR codes.

Some tips if you try this at home... QR codes come in multiple sizes with various levels of error correction. The minimum size is 21x21 but many QR websites will generate larger ones. Avoid the larger sizes unless you want to do more assembly. I used the Raco Industries online QR code generator since that site provides a lot of control over the generated QR code. If you print out the code with .3125" pixels, the output will conveniently match the size of the Lego blocks.

(Apologies if you were expecting some Arc code in this article.)

The rise of scripting languages and the fall of Java

Java is very much in full retreat.
-- R. Loui
Professor Ronald Loui has an interesting article on the rise of scripting languages (In Praise of Scripting: Real Programming Pragmatism) in the July 2008 issue of IEEE Computer. It claims scripting languages such as Perl, Python, and Javascript have dramatically fulfilled their early promise, provide many benefits, and are poised to take over the lead from Java. However, the academic programming language community is stuck in theory and hasn't recognized the ascendence of scripting languages.

I agree that scripting languages are on the rise. Most people would agree that they provide rapid development, higher levels of abstraction, and brevity that helps the programmer. The article also describes how scripting languages can be a performance win, since they can allow experimentation and implementation of efficient algorithms that would be too painful in Java or C++. So even if C++ is faster on the micro-benchmark level, a programmer using a scripting language may end up with faster algorithms overall. I've argued somewhat controversally that Arc is too slow for my programming problems, so I remain unconvinced that basic performance can be ignored entirely.

As for the claim that Java is in full retreat, it strikes me as wishful thinking. (I'd believe "slow decline" though.) It will be interesting to check back on this claim in 5 years.

I personally believe that CS1 [freshman computer science] Java is the greatest single mistake in the history of computing curricula.
-- R. Loui
The article suggests good languages for teaching introductory computer science are gawk, Javscript, PHP, and ASP, but Python is emerging as a consensus for the best freshman programming language. This is the hardest part of the article for me to swallow. The idea of writing real programs in Awk never occurred to me, and I remain skeptical even though the author claims it works well. For those who would suggest Scheme as an introductory programming language, it was displaced as a dominant freshman language by Java a decade ago, and is apparently no longer considered an option.

I can't argue with the author's claim that student learning is enhanced by experimenting, writing code, and getting hands-on experience, and that scripting languages make this faster and easier.

Python and Ruby have the enviable properties that almost no one dislikes them, and almost everyone respects them.
-- R. Loui
In Why your favorite language is unpopular I discussed how the Change Function model can explain the success of programming languages based on maximizing the crisis solved and minimizing the perceived pain of adoption. I can apply this model applies to scripting languages as well:

Magnitude of crisis solved by Tcl/Tk: High - How to add a scripting language to a C program. How to add a GUI to a C program without painful X11 and Motif code.
Total Perceived Pain of Adoption: Low - Link Tcl in with your C program and add a few hooks. Create the GUI with trivial scripts.

Magnitude of crisis solved by Perl: High - How to quickly write CGI scripts. How to solve problems too complex for shell scripts. How to process files. How to develop quickly and iteratively.
Total Perceived Pain of Adoption: Low - Apart from looking like line noise, Perl is easy to get started with, is well integrated with Unix, has the definitive regex implementation, and has libraries for almost everything.

My point is that these languages solved specific painful problems and had low pain of adoption. As a result, they were much more successful than beautiful, powerful languages that were less able to directly solve painful problems or were more painful to adopt.

The real reason why academics were blindsided by scripting is their lack of practicality.
-- R. Loui
A major thrust of the article is that academics are too concerned with theoretical issues of syntax and semantics, rather than pragmatic issues of what a language can achive quickly, inexpensively, and practically. Academics are said to be too tied to theoretical concepts such as object-oriented programming and strong typing, and are missing the real-world benefits of scripting languages.

(Interestingly, Rob Pike made a similar argument against academics in the context of operating systems software (Systems Software Research is Irrelevant), stating that academic research is irrelevant and the real innovation is in industry. Since I have friends doing academic OS research, I should add a disclaimer here that I don't necessarily agree.)

One measure of pragmatics raised by the paper is how well does a language work with other Unix tools. I think the importance of this is underappreciated. In particular, I view this as a significant barrier to adoption of Arc. Running Arc as a shell script instead of a REPL is nontrivial (as is the case with many Lisp and Scheme implementations). Running an external program from Arc is clunky, even though it is often necessary to actually get things done (Kens' law), and real pipes are missing from Arc entirely.

Java's integration with Unix also has painful gaps - where's getpid() for instance? Why is JNI so difficult compared to calling native code from C#? I blame Sun's pure-Java platform independence ideology, and I'm surprised it hasn't hurt Java more.

On the other hand, Python and Perl provide a remarkable degree of integration, which I view as a key factor in their success. Likewise, Visual Basic is highly integrated with the Windows environment and highly successful there.

In conclusion, Loui's paper raises numerous interesting points about the success of scripting languages. I expect that the reasons for the rise of scripting languages will only get stronger, and languages that don't support the scripting model will have an increasingly harder time gaining adoption.

Note: quotes above are from the preprint and may not match the published article.