An avian carrier's blog – Programming

People programming for the Android platform know that you are not supposed to perform lengthy operation in the user interface task. You must create a background task, which will interact with your user interface task through a Handler, or you will use a pre-built AsyncTask to ease the interaction.

However, if you chose to use Scala instead of Java to build your Android application, you can easily take advantage of its functional nature to build much more exciting constructs to handle this mandatory parallelism. For example, while developing a piece of code to retrieve the state of my city shared bike stations from the network, I wrote a little piece of utility code based on two functions each taking an expression to run: onBG executes something in a background task, and its companion onUI executes something back in the user interface task. Also, when calling onUI, the result of the given expression can later be used from the background task; if needed, it will block until this result is available.

Here is a short example showing the loading of the bike stations list from the network, then the loading of the state of the first five stations. A progress dialog, part of the user interface, indicates the current state of the background operation. Compare to what you would have needed to write in Java.

    // Execute lengthy loading from the network in a background (BG) task as to not
    // block the user interface (UI) task.
    this.onBG {
      // Create a progress dialog on UI task, and return a pointer to it which, if
      // used, will block as long as needed until the expression has terminated.
      // Otherwise, do not block.
      val progressDialog = this.onUI(ProgressDialog.show(this, "Loading stations",
                                                         "Loading list of stations"))
      try {
        // Load a list of stations from the network (long operation) and keep only
        // five of them.
        val stations = Station.loadFromNetwork.take(5)

        // Change the progress dialog so that now it can be used to indicate
        // the progress while station information is loaded from the network.
        // This has to be done on the UI task. Note that this will wait until
        // the progress dialog creation has terminated if needed, as we use
        // the result of the previous "onUI" call.
        this.onUI {
          progressDialog.setIndeterminate(false)
          progressDialog.setMax(stations.size)
        }

        // For every station…
        for ((station, index) <- stations.zipWithIndex) {
          // …update the progress dialog on the UI task…
          this.onUI {
            progressDialog.setProgress(index)
            progressDialog.setMessage("Loading station details\n" + station.name)
          }
          // …and load its availability from the network.
          station.reloadAvailability
        }
      } finally {
        // Whatever the completion is (regular or exception), dismiss the
        // progress dialog.
        this.onUI(progressDialog.dismiss)
      }
    }

Why did I write those two functions? Just because, in Scala, I can.

Don't wait: try Scala today.

Every year since 2003, Alexis Polti and myself run a course named "ROSE" (Robotique et Systèmes Embarqués, Robotics and Embedded Systems) for future engineers at Télécom ParisTech. During this 120 hour curriculum, students have to design and buid embedded systems, including designing their own electronic boards and programming them. Classical courses are limited to the minimum (real-time operating systems, signal integrity), and students must learn by themselves all the other topics while the two teachers offer lots of assistance (we are physically with the students most of the time to answer their questions).

As every year, the 2011 occurrence introduced some changes (hopefully for the better), that I now want to analyze.

Afterthoughts

Git vs. Hg

Until last year, we were using Mercurial as our revision control system because we thought it was simpler to use than Git for the students although the teachers both used it. We decided to try Git with the Gitolite backend tool that we already used for research projects. The outcome was unexpectedly successful: every project used lots of branches for their development, merging and rebasing at will.

The presence of Clément Moussu, a student who had previously done an internship at Gostai where Git is used intensively (they even use "git notes" that almost noone knows about), has been a tremendous help, and has been acknowledged during the debriefing session by other students. He and three other students explained Git to the others, and spoke about the best practices right from the beginning. So we plan to keep using Git as our preferred revision control system.

Linux-based boards

For the first time, we accepted that some projects use Linux-based boards in addition to the micro-controllers boards they had to design. The mix of those Linux-based boards (one Armadeus APF27, one BeagleBoard xM and one Gumstix Overo FE COM) allowed them to use high-level languages (Python), libraries (OpenCV, 0MQ) and cloud-based processing capabilities (Google Appengine) very easily. We plan to keep this possibility as well, but we need to ensure that every project needs to build additional micro-controller based boards as we want our students to really know how to design a board from scratch.

Best programming practices

This is something we did not do: ensure that our students know the best programming practices. Next year, we plan to do a live-coding session where we will collectively try to write the best possible code. The teacher will write, compile and run the code as suggested by the students, and explain how the code may be improved and what needs to be done to guarantee reliability and ease of maintenance. Tricky exercises will be proposed, to ensure that students need to know when volatile needs to be used, and when it is not needed. Also, lockless algorithms, depending on the underlying hardware, will be used whenever possible. The effect of inlining some functions (and when not to inline and let the compiler work it out) will be studied intensively, and methods to avoid any code duplication will be taught.

Some students naturally know how to write good code, but some don't and just write code that works but is unmaintainable. Instead of having them fix the code afterward, we will make sure that they write proper code from day one. So next year, the students will learn this skill at the beginning of the class rather than along its course.

The projects

If you are curious to see what has been done, here are links to the various projects done by the students in 2011 during this 2.5 month course:

• Casper: a talking and listening robot shaped like an elephant trunk
• Copterix: a helicopter with eight engines
• IRL: a nightclub laser that displays your tweets and let you control via Twitter the color of the club as well as other equipment such as the smoke machine
• MB Led: a very nice set of blocks letting you play games by moving them around
• Rosewheel: a Segway clone, remotely controlled using an Android phone
• TSV Safe Express: control a model railroad layout using cheap components (unfortunately, the web site is almost empty)

Geocaching is a worldwide outdoor treasure hunt game in which you have to locate and find hidden tokens by using a GPS receiver. Not only is this game a good way of discovering new places, it may also contain real brain teasers if you have to solve puzzles to find the right coordinates. I have been enjoying this activity since nearly 8 months now, and have already discovered more than 100 geocaches in 11 different countries.

Unfortunately, the biggest geocaches database is located on the geocaching.com web site. This site does not offer any API letting you access your own data, let alone information on geocaches. If you happen to be a paying member (as I do), you can generate what they call pocket queries: those are database runs, triggered manually or at scheduled times, listing basic geocaches information for a limited area or around a given path. Those pocket queries must then be transferred to your GPS device or your smartphone. When you want to log the fact that you have discovered a cache and let a comment to the geocache owner, you have to once again log onto the web site and do it manually. The terms of use prohibit you from using any robot to automate those tasks.

A SOAP API exists, but its access is reserved to trusted partners (read: paying partners who themselves charge a recurring fee to their users). An official Android application has been developped by Groundspeak, the owner of geocaching.com, but it is priced much higher than typical Android applications and has much less features than c:geo, a wonderful rogue application which scrapes the geocaching.com web pages on your behalf. Also, since it parses HTML page in order to extract the needed information, c:geo needs to be updated each time the web page presentation gets changed.

This excellent post from Scot Hacker's Foobar Blog hits the nail on the head, and what was written in 2008 is still valid in 2011:

This blew my mind. The culture of the site is so web 1.0 that a basic question about interoperability was met with distrust. Not only is geocaching.com lacking the technology it needs to enter the web 2.0 world, it’s lacking the culture needed to support it. In 2008, interoperability between sites needs to be encouraged, not discouraged. Sad that geocaching.com’s traditional closed-ness has created this kind of culture.

[...]

The irony is that geocaching.com relies so heavily on the open APIs provided by Google and other mapping services, but provides no open-ness back to the web in return. Imagine using geocaching.com without the map mashups integration – it would be nearly impossible. One would think that the folks at geocaching.com would see their own mashups as an example of the great ideas that bloom when datasets and APIs are open and shared.

But the world of geocaching may be changing soon: Garmin, the well-known GPS receiver maker, recently announced the launch of opencaching.com. I hope that many geocachers will register their caches and their finds on this site, and that many applications will take advantage of their publicly usable API. On Android, Cache Me seems to be the first application using opencaching.com data. I hope that c:geo will soon be able to use those liberated bits as well.

I'll follow Dave Ray and will try to say something nice about a bunch of programming languages I use or have used seriously:

• Ada – The only language I would trust my life to.

• C – It gets things done easily in a controlled space when resources are scarce. I use it in many embedded situations, often with FreeRTOS.

• C++ – Its templating system with specialization beats everything I know. When I worked on Urbi at Gostai, I had a lot of pleasure using it.

• Erlang – The language to use to develop distributable parallel applications. I wrote many programs for research projects with it.

• Factor – One of the languages I feel the most comfortable with. I really like the reverse polish notation and the powerful combinators. I use it for many personal and teaching projects.

• Forth – Forth is one of the languages that I have been liking since the first time I heard about it. Its conciseness, simplicity, grammar and ease of implementation beats almost everything when it comes to size on very small embedded systems. I used it to write a Forth compiler targetting the Microchip PIC16Fxxx microcontrollers family.

• Haskell – I started using it when I had to send patches for Darcs. I really love monads, and I also love explaining them in class. My window manager configuration is also written in Haskell.

• J – It is unbeatable if you have RSI and need to type as little characters as possible for a task that can be applied to a whole array. I use it mostly to solve Project Euler problems.

• Java – Well, everyone knows it so it may be used to explain a simple concept. Is that nice enough?

• Javascript – Javascript lets us do things in the browser I would not have imagined five years ago. For example, this web page is static but includes Twitter updates and comments, thanks to Javascript. On the server side, I use it within a CouchDB database where I store a whole web application; it dynamically generates iCalendar views for multiple people from data gathered at TVrage.com using their XML API.

• Python – I can hack anything in a few minutes and still be able to read it later. I wrote a Forth compiler for the Microchip PIC18Fxxx microcontrollers family with it.

• Ruby – Feels like Python, only more functional and cleaner. I would use it more if I had not been bitten by threading unstability on Sparc64Linux in the past (for the will-spam-for-food.eu.org service we ran with Pierre Beyssac and Thomas Quinot). Ruby helps me run this blog.

• Scala – There comes a useful, powerful and pleasant to use language targetting the Java virtual machine. I used it to write my HarassMe Android application.

I probably forgot some languages in the list. However, if I use them, I am sure I can tell something nice about them.

I stumbled upon several questions on StackOverflow where people asked about safely interrupting distributed workers communicating through the ØMQ middleware.

Most of the ØMQ examples describing workers pools assume that jobs are pushed to the workers in a round-robin way. The first worker receives a job, the second one receives a job, and so on, then the first worker receives yet another job, the second one… Well, you get the idea. Unfortunately, not all jobs are necessarily created equal, and the workers may be running on computers with different processing capabilities and workloads.

As an example of a different way to do it, I wrote a simple Python broker named that distributes tasks on demand. When a worker is ready to work, it asks for some job to perform, receives one if one is available, does the computation, and sends the answer back. This way, no task should ever be sent to a worker which is busy doing other things, possibly for a long time.

The broker also checks that the answer to a job comes back within a given time-frame. If it does not, it assumes that the worker has crashed or is overwhelmed by other tasks, and sends the job again to another worker. Another parameter may be specified: the number of times to attempt to run each job. If a job description causes workers to raise an exception repeatedly, it may be a good idea to abort it and not try to run it indefinitely. If a job is aborted by the broker, an empty answer will be sent to the client so that it knows that its request could not be completed.

Of course, this sample broker is far from perfect, and many things could be changed for the better:

• If the broker is restarted, workers will not receive tasks anymore. This can be easily fixed by having the broker reissue their task requests from time to time, which would require using a XREQ ØMQ socket instead of a REQ one to allow out of sequence exchanges.

• If the broker is restarted, queued requests will be lost. Each request could be accompanied by an unique id generated by the client, and asked about if the answer does not arrive in a given time. This would also give a way to cancel pending requests if the client realizes that it does not need them to be executed anymore.

• Timeouts and number of retries could be configurable for each request rather than globally.

Nonetheless, it should be enough to answer some questions and show how to do things differently.

A sample worker module is also available in the repository. It provides a Worker class that can be derived from; one must also override one of the process or process_multipart method with a function doing the real work in the child class. The inherited methods will take care of communicating with the broker.

Getting zmq-broker

You can get the current development version of zmq-broker using git:

git clone git://github.com/samueltardieu/zmq-broker.git

This will create a zmq-broker directory in which you will be able to record your own changes.

You can also browse the zmq-broker repository on GitHub.

Contributing to zmq-broker

Reporting bugs and asking for features

If you find a bug or have an idea for a new feature, you might consider adding a new issue. The more precise you will be in your description, the more useful it will be.

Submitting patches

Patches are gladly accepted from their original author. Along with any patches, please state that the patch is your original work and that you license the work to the zmq-broker project under a license compatible with the current one ().

To propose a patch, you may fork zmq-broker repository on GitHub, and issue a pull request. You may also send patches and pull requests by email.

Before I use Jekyll, Wordpress was running my blog. One thing I noticed while using Wordpress was that Google and other blog search engines were fetching my new posts a few seconds after I published them.

To achieve these performances, Wordpress use two different systems:

1. It sends a ping to some services which in turn fetch your feeds. Some concentrators such as ping-o-matic allow you to ping them, and they in turn ping various search engines for you so that you don't have to. Then each search engine decides whether or not it will crawl your blog again.

2. Wordpress also uses the recent pubsubhubbub protocol (what a lovely name!) In your feed, you declare the address of a hub where interested parties can send subscription requests. Then, when a new article is published on your blog, Wordpress sends a ping to the hub, and the hub retrieves your feed. If the feed has changed, it is sent to the subscribers using a callback address they registered when they subscribed. This way, interested services such as Google do not have to retrieve the feed themselves, as it will get pushed to them when it contains new items.

It is easy to enhance a Jekyll blog with the pubsubhubbub system, because:

• there exists public open pubsubhubbub hubs, such as the well known https://pubsubhubbub.appspot.com;
• you may send the ping message from everywhere, not necessarily from the server.

The first thing to do is to add hub information in your Atom or RSS feeds. For an Atom feed, you may add the following into the feed section

<feed xmlns="http://www.w3.org/2005/Atom">
  <link rel="hub" href="https://pubsubhubbub.appspot.com"/>
  ...
</feed>

while a RSS feed would contain

<rss xmlns:atom="http://www.w3.org/2005/Atom">
  <channel>
    <atom:link rel="hub" href="https://pubsubhubbub.appspot.com"/>
    ...
  </channel>
</rss>

Then you may want to ensure that you can tell the hub that your feed has some fresh interesting content by pinging it. If you don't, your feed will be retrieved at regular intervals, but you will lose the benefit of using pubsubhubbub. If you are using rake for your development, you may want to create a :ping task which will send the ping when you run it:

desc 'Ping pubsubhubbub server.'
task :ping do
  require 'cgi'
  require 'net/http'
  printHeader 'Pinging pubsubhubbub server'
  data = 'hub.mode=publish&hub.url=' + CGI::escape("http://address.of.your/feed/")
  http = Net::HTTP.new('pubsubhubbub.appspot.com', 80)
  resp, data = http.post('http://pubsubhubbub.appspot.com/publish',
                         data,
                         {'Content-Type' => 'application/x-www-form-urlencoded'})

  puts "Ping error: #{resp}, #{data}" unless resp.code == "204"
end

If you prefer to use make, then a similar target using wget or curl would do the job. The only thing you need to do is send a POST request to http://pubsubhubbub.appspot.com/publish with an URL-encoded form containing the following two fields:

• hub.mode: a single string publish.
• hub.url: the URL of your updated feed. This can be repeated multiple times if several feeds have been updated at once.

Note that in the real life, my rake rule is much more complex: since I have separate feeds for the two languages I use on this blog, as well as one feed per tag, my Rakefile contains code to check whether posts have been updated in the last 24 hours, and all the feeds that might have changed (and only these) will be signalled to the hub.

What can you do with those realtime updates? You can start using services such as twitterfeed to post twitter notices of your blog posts right after they appear on your site, or you can use PuSH Bot to get live updates in your XMPP stream (in Google Talk for example). This is really as easy as pie, there is no reason your blog should not be using it right now.

How will I publish this very post? I will just do

rake install ping

and be done with it.

Since I now use Jekyll to generate this web site, I had to find a way to convert tag names into nice ASCII-only-lowercase symbols. For example, Free Software would become free-software and Éducation would become education.

One solution I came up with is a slugify filter which uses the unicode ruby gem. After converting the string to lower case and decomposing æ and œ to ae and oe respectively, it uses the unicode normalization form KD which separates individual characters from accentuation marks as shown in this figure. Then only plain ASCII letters are kept, spaces are replaced by hyphens, and the string is reassembled.

# -*- coding: utf-8 -*-
module Slugify

  require 'unicode'

  def slugify(input)
    t = Unicode::nfkd(input.downcase.gsub('æ', 'ae').gsub('œ', 'oe'))
    t.gsub(/[^\w\s-]/, '').gsub(/[\s-]+/, '-').downcase
  end

end

This way, I can link to the tag page using <a href="/blog/tag/{{ tag | slugify }}">{{ tag }}</a> without fearing that some software chokes on the URL. It works well and I am now satisfied with this function, so I removed the questions that were there in previous instances of this post. The only thing I dislike is the double downcase call, due to the fact that some entities cannot be downcased without knowing more about the used language.

Edit: updated to match the name and behaviour of Django's slugify as per Ricardo Buring comment with an additional "æ" to "ae" and "œ" to "OE" translations.

I just released AdaSockets 1.8.7. This is a maintenance release only, to adapt to the upcoming GCC 4.5.0 new Ada style warnings.

A friend of mine challenged me today to the number game. This is a classical one, where you have to guess a number between 0 and 999, and the computer will tell you whether you were right on or if you were above or below the chosen number.

Instead of doing dichotomy by hand or with a calculator, I wrote the following Forth snippet using the gforth interpreter:

: guess 2dup + 2/ dup . ;
: init 0 999 guess ;
: big nip guess ;
: small -rot big ;

Here is the transcript of an interactive session (what I typed is in black, what was printed by gforth is in red):

init 499 ok
small 749 ok
small 874 ok
big 811 ok
big 780 ok
big 764 ok
small 772 ok
big 768 ok
big 766 ok
big 765 ok

For those not well-versed in Forth, here is how it works:

• guess takes the low bound and the high bound from the stack, put them back there and adds the middle value as well, and prints it.
• init starts a session by putting 0 and 999 on the stack and calls guess to print the initial value to be entered.
• big removes the high bound from the stack, leaving only the low bound and the previous middle value, then calls guess to get a new value.
• small replaces the low bound on the stack by the previous middle value, and calls guess. The stack manipulation and the call of guess would be done using -rot nip guess, and I took advantage of big by factoring it into -rot big.

That’s it. Who could now pretend that small isn’t beautiful?

Tonight, I was willing to create a while construct in Factor taking two items on the stack:

1. a quotation to execute when the test is true
2. a test quotation

For example, I wanted to be able to find the smallest power of two greater than or equal to an arbitrary number (here 34098) by doing:

1 [ 2 * ] [ dup 34098 < ] while

(of course there are much better ways of doing that, such as 34098 2 * 1 + 2 /i but that's not the point here)

This would be much easier if we could recurse from within a block (by using a recurse word). Let's start with that:

SYMBOL: recursive-block

: set-block ( quot -- )
  recursive-block set ;

: recurse ( quot -- )
  recursive-block get call ;

: with-recurse ( quot -- )
  recursive-block get >r
  dup set-block call
  r> set-block ;

A quote passed through with-recurse can use the recurse word and re-execute itself.

Now that we have recursion, it is easy to implement while using currying:

: while ( quot quot -- )
  swap [ call recurse ] curry [ slip when ] 2curry
  with-recurse ; inline

Note that inline is used here to give the optimizing compiler a chance to build the complete quotation at compile-time if both quotations given to while are statically known.

To create a vocabulary recursion containing this code, one can create a file extra/recursion/recursion.factor containing:

USING: kernel namespaces ;
IN: recursion

<PRIVATE

SYMBOL: recursive-block

: set-block ( quot -- )
  recursive-block set ;

: init-block ( -- )
  [ "recurse called without with-recurse" throw ] set-block ;

PRIVATE>

: recurse ( quot -- )
  recursive-block get call ;

: with-recurse ( quot -- )
  recursive-block get >r
  dup set-block call
  r> set-block ;

: while ( quot quot -- )
  swap [ call recurse ] curry [ slip when ] 2curry
  with-recurse ; inline

MAIN: init-block

Loading this library can be done by issuing the following command in the listener: "recursion" run.

That's all folks.

Today, a friend of mine told me that he was writing a Sudoku solver in Haskell. I could not resist and also wrote a brute-force one. The code is ugly (I was trying to generate as short a program as possible), but it led me to interesting thoughts.

First, here is the code. Beware, you are supposed to know Haskell and monads to understand the comments following the code:

import Control.Monad (msum, mzero, MonadPlus)
import List (elemIndex, (\\), intersperse)
import Maybe (fromJust)

get s (l, ln, c, cn) = [s!!(ll*9+cc) | ll <- [l..l+ln], cc <- [c..c+cn]]
getall n s = [(f 0 9 1, 0, 0, 8), (0, 8, f 9 1 1, 0),
              (f 0 27 3, 2, f 9 3 3, 2)] >>= get s
    where f m d t = ((if m == 0 then n else n `mod` m) `div` d) * t

solve :: (Eq a, MonadPlus m) => [a] -> a -> [a] -> m [a]
solve g n s = case elemIndex n s of
              Nothing  -> return s
              Just idx -> msum $ (g \\ getall idx s) >>= \x ->
                     return $ solve g n $ take idx s ++ [x] ++ drop (idx+1) s

showSudoku s = unlines $ "Solution:" : (flip map [0..8] $ \n -> sline n s)
    where sline n s = concat $ intersperse " " $
                      map show $ get s (n, 0, 0, 8)

main = do
  s <- getContents
  let display = do
         choice <- solve [1..9] 0 $ map read $ words s
         return $ showSudoku choice
  putStr $ fromJust display

The interesting piece here is not the code itself, which is indeed pretty boring and unclear, it is the type declaration of the solve function: its return type is m [a], where [a] represents a completed Sudoku grid and m is a MonadPlus instance. What is the point of choosing a MonadPlus type when, in the main function, the result is coerced to a Maybe (which is a MonadPlus instance) before being printed by the usage of fromJust?

The Maybe type can contain zero or one result. It means that the code, when executed, will either find no solution or return exactly one solution which will then be printed. But what can we change if we want to print all the solutions? (if we start from the empty grid for example)

We are using Haskell after all. Instead of using a Maybe type, we might as well use a list. All right, the list type is also an instance of the MonadPlus class. It can contain nothing (empty list), one result, or more. Let’s change the line containing fromJust in main by:

mapM_ putStr display

The use of mapM_ coerces the use of solve to a list type. Now, all the solutions will be printed, not only one of them.

If you want to try it, create a file called empty containing 9 lines of 9 space-separated zeroes:

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

and compile the program (either variant). Then you can feed it the empty sudoku grid:

% ghc -o sudoku sudoku.hs
./sudoku < empty

Monad matters. For real.

I may be the happiest computer-science teacher in the world: in less than three months, I will start teaching a whole new class called “non-classical paradigms and languages”. The goal is to let students pursuing their masters degree discover and manipulate concepts that they haven’t had a chance to play with when using mainstream languages (C, C++, Java and Ada being the ones they have been taught so far).

I do not want my students to know every language on the earth. However, I want them to be able to recognize that the problem they have in their hands could be more elegantly solved using continuations, or that embedding a Forth-like interpreter would make their program easier to test and extend.

Now comes the difficult part: what languages should I teach and what paradigms should I show? I have 60 hours at my disposal that I can freely dispatch between theory and practice (labs). Since I will be leaving tomorrow for one week, I thought it would be a good idea to let people comment, either publicly (use a comment) or privately, on some of the ideas I got so far.

The students already know C, C++ and Java quite well, and most of them have already played with Ada, Lisp (although only at a very basic level) or Prolog.

Below you can find an HTML export of the Freemind map I used to structure my thoughts. I did it in 10 minutes, so it is neither complete nor well organized. Do not hesitate to throw in new ideas or languages. The main constraint is that the students must be able to get the same environment at home as in the labs, meaning that a good Free Software implementation must exist (and will be used in labs). The only exception might be J if it gets included in the course as the language itself is very interesting (and simpler to use than APL on modern machines), and a free (gratis) implementation exists and runs on most platforms.

• Concepts
  
  • Continuations
  • Stack-based languages
  • Image-based languages
  • Portable environments
  • Parsing, interpretation, compilation
    
    • Macros
    • Compile-time evaluation
    • Creation of domain-specific languages
    • Reflexivity
    • Code is data is code is data
  • System integration
    
    • Transparent parallelism
    • Live code update
    • Message passing and mailbox system
  • Functional programming
    
    • Lambda expressions
    • Closures
    • Lazy evaluation
    • Promises
  • Other flavours
    
    • Declarative languages
    • Languages working on arrays
  • Embedded interpreter
• Languages
  
  • Common Lisp
  • Scheme
  • Smalltalk
  • J
  • Forth
  • Factor
  • Haskell
  • Erlang
  • LUA
  • Python
• Open questions
  
  • Common Lisp or Scheme ?
  • Forth or Factor ?
• Various
  
  
  • Implementations should be free software
  • No brainfuck, intercal, befunge, etc.

On his blog, tickletux advocates the use of FizzBuzz to find developers who grok coding. However, this kind of test may also cause difficulties. What do you do if a candidate answers with the following (correct) C code?

#include <stdio.h>

static const char *t[] = {"%d\n", "Fizz\n", "Buzz\n", "FizzBuzz\n"};

int main()
{
  unsigned int i;
  for(i = 1; i <= 100; i++) printf(t[3&19142723>>2*i%30], i);
  return 0;
}

What explanation (and action) would you choose?

• the candidate is smart and managed to avoid any explicit test (“branches are evil” philosophy): hired;
• the candidate tried to impress you and won’t explain the 19142723 in her code: she is likely to cause problems in the team: not hired;
• the candidate mind is so convoluted that she could not think of another solution: not hired
• the problem you gave the candidate was so boring that she solved it while having some fun; may be a real problem solver: hired;
• the candidate is perfectly suited for an embedded systems programmer position: hired or not, depending on the kind of software you want her to write.

If I were to interview people for a programmer position, I honestly don’t know what I would do with someone writing such a code in response to the original problem. I would probably assume that the programmer was bored and that she wanted to have some fun while doing her job, and I kinda like this idea.

As you may already know, I'm a big fan of stack-based languages such as Forth, functional languages such as Haskell and reflexive languages such as Smalltalk. You can imagine how happy I was when I discovered Factor a few days ago: it combines all those aspects.

Today, a friend sent me someone email signature and asked me if I could decipher it:

01101001001000000110011001110101011000110110101101100101011001000010
00000111100101101111011101010111001000100000011011010110111101101101
00001101000010100110000101101110011001000010000001101110011011110111
01110010000001100110011011110111001000100000011110010110111101110101

As any programmer on the Earth would have, I immediately assumed that those were ASCII codes printed in binary format. I had a Factor interactive shell opened in one of my windows, so I cut and pasted the whole string (surrounded by quotes) and entered:

8 group [ 2 base> ] map >string print

and the cleartext version appeared instantly. All in all, it took me around 20 seconds to uncover the original text using Factor.

How does this work? Factor is a stack-based language, meaning that data are put onto a stack and words (equivalent of functions in other languages) use the data on the stack and put results there. Factor is a (dynamically) typed language: complex data can be pushed onto the stack, while untyped languages such as Forth can only push numbers there.

Writing the string pushes it on the stack. Using

8 group

takes the string on the top of the stack, considers it as a sequence (a succession of characters), group them by eight and returns an array of strings of length 8. At this point, there is only one element on the stack: an array of eight-characters-long strings.

Then

[ 2 base> ]

pushes another element on the top of the stack: a quotation (the equivalent of a lambda expression in functional languages), which is a block containing code. The base> word consumes two elements from the stack, a string S and a number B, and pushes back a number which is the value represented by S in base B. For example, the expression

"01101001" 2 base>

will let the value 105 on the stack, as 01101001 in binary represents 105 in decimal.

map

takes a sequence and a quotation. It represents the classical map operation in functional languages: it applies the quotation to every element of the sequence and gathers the results in a new sequence. As a consequence, each eight-characters-long string gets transformed into its decimal representation. At the end, we end up with a single element on the stack, which is an array containing all the ASCII codes of the sentence.

>string

transforms a sequence of ASCII codes into the corresponding string. Then

print

is similar to C's puts and prints the string on the standard output while recognizing special sequences such as \r and \n.

The content of the unencrypted text itself is not important; my point is that Factor is very compact and its stack-oriented nature helps writing concise and clear programs. For example, here is one of the many possible implementations of the reverse functionality: it takes a string from the stack and lets its ASCII representation in binary onto the stack.

[ 2 >base 8 CHAR: 0 pad-head ] [ append ] map-reduce

I'm sure that you're thrilled to know that "Hello, world!" encodes as

0100100001100101011011000110110001101111001011000010
0000011101110110111101110010011011000110010000100001

(edited on 2009-06-13 to use pad-head and map-reduce)

As an experienced programmer, I participate in many Free Software projects when time permits. I am committed to a few projects, and I frequently submit patches to random projects that I happen to bump into. I also understand the dynamics of free software: when a bug stands in my way, I often fix it myself rather than waiting for another contributor (who may have her own priorities and agenda) to fix it. Same when I badly need a feature.

In this post, I will compare the submission process of two changes I made to free software recently:

• a new watchdog driver for the Linux kernel;
• a fix for a critical flow in SIP message handling in the Asterisk telephony system.

Linux device driver

I first posted my new device driver code as a patch (a difference between the actual Linux source code and the modified one) on the linux-kernel mailing-list. Shortly after that, some people publicly answered my mail and offered remarks and criticisms about my changes. Most of the advices were well targeted and I modified my patch accordingly. Some of the remarks were a bit off because people commenting the code hadn’t read the device datasheet and were confused by some names used therein and mirrored into the driver; I explained the situation and why I would not act upon those remarks. One point about a possible concurrent access was discussed and resolved after a few technical exchanges. I then posted a modified patch for everyone to comment on. This later patch was then acked (i.e., blessed) by a major developer.

Various parts of the Linux kernel are maintained by different people. The device I was addressing was a watchdog (a piece of hardware that forcibly reboots your computer if the operating system fails to say “I’m still alive” on a regular basis), so the watchdog subsystem maintainer took responsability and integrated it into his own development tree, so that people willing to test this new driver could do so easily. After some time, while the new driver had shown not visible disturbance of the rest of the kernel, it was pulled by Linus Torvalds into the main Linux kernel tree and was released as part of Linux 2.6.19.

Note that when the watchdog subsystem maintainer integrated my new driver into his tree, he was already quite confident that the driver was clean as it had been carefully read and commented on by several other developers. The integration within his tree rather than into the main Linux kernel ensured that all the watchdog drivers can play nicely together.

Asterisk flaw in the SIP engine

Free Telecom is the second most important ADSL provider in France. They provide a triple-play service over ADSL: IP, telephony and television. The telephony service can be accessed either using an analog phone connected to their ADSL modem or using a SIP connection to their server. On the server side, Free Telecom chose to use a solution by Cirpack, made from boxes able to handle several thousands of simultaneous SIP sessions.

When the Cirpack server was upgraded at the beginning of December, all Asterisk boxes using Free Telecom as their SIP provider immediately stopped working: the voice was not going through anymore. This problem was signaled onto a forum by an Asterisk user a few hours after the upgrade and promptly analyzed by a Cirpack engineer: it appeared to be a flaw in Asterisk SIP handling. The engineer rolled back the Free Telecom server to the previous revision and sent me a mail with the description of the problem. Why me? Because we know each other as we studied together, and he knew I was using Asterisk to connect to the Free Telecom SIP server and that I was likely to quickly investigate and fix the problem.

A few hours later, I produced two short fixes for Asterisk and was able to test them against a Cirpack server running the new firmware. Everything went fine and the problem was fixed. I posted the patches to the Asterisk bug tracking system and, less than four hours later, added full debugging information with and without the patches at the request of a manager so that it was clear what the problem was and how the patch fixed it.

I also sent several mails on the Asterisk developers mailing-list to underline the importance of the flaw. As long as the flaw is not fixed, any upgrade made by a VoIP provider may break all its Asterisk clients without any easy workaround. To describe the flaw shortly, an unpatched Asterisk doesn’t understand perfectly valid SIP headers and interprets them in a totally wrong way, causing the subsequent traffic to be sent to the wrong place.

Asterisk 1.4.0 was released 19 days after I explained this critical flaw and posted the patches to correct it. Not only were the patches not included in the release, but as far as I can tell no peer review has occurred on the patches. The only request made by a manager was that some developers, who have not yet answered, test the patch.

Also, at some point, this very same manager added a relationship between this problem and another one without any comment to explain this alleged relationship. As far as I can tell, the two bugs are totally unrelated and I fail to see any relationship between them except that they address two problems in SIP message processing, although one is about SIP headers syntax and the other one about the SIP engine internal state machine.

At this point, it is worth noting that I do not feel bad about Asterisk because my patches were not included in the latest release; what I criticize here is what I consider a lack of feedback on user-contributed fixes and a lack of interaction between developers.

Comparing the two processes

Proposed changes to the Linux kernel are posted on a public mailing-list as plain-text, where anyone is free to comment on them. The plain-text format makes it easy to intersperse the relevant code portion with the comments. One or several structured discussions follow, each one addressing one aspect of the proposed patch. New versions of the patch may then be proposed and discussed until the patch is finally blessed (acked) by one or more fellow developers. Note that this process happens in an email client, without any compilation taking place at this stage. Technical flaws may be found by code reading and discussion rather than by testing whether the code seems to trigger a bug or not. Also, if the code would benefit from extra documentation, such documentation will be requested publicly by other developers.

Proposed changes to Asterisk are posted onto the Asterisk bug tracking system maintained by Digium (the original authors and the current maintainers of Asterisk). A disclaimer also needs to be filled by contributors, as Digium wants to be able to make a proprietary version of Asterisk, while others may only distribute it as a GPL software. I have the impression that the patches are not peer reviewed: the use of a bug tracking system doesn’t ease such a code review process, compared to a mailing-list as in the Linux kernel patches case. I am also under the impression that patches are tested rather than being read first. If enough developers report that the patch hasn’t visibly broken their system, the patch may eventually be integrated.

Also, parts of Asterisk sometimes undergo major rewritings without any attempt to explain what has been changed exactly. For the Linux kernel, it would be unacceptable: a serie of incremental patches would be required to be submitted on the mailing-list, with a step-by-step justification of why things need to be changed. When incremental patches are not doable, because changes depend on each other, separate patches that need to be applied at the same time will still be required so that individual changes are reviewable by other developers.

As you may have guessed at this stage, I much prefer the Linux kernel way of doing it. The peer review system exposes proposed changes to several pairs of hackers eyes. The patches and the subsequent discussions also teach potential contributors what they need to send and how they need to present it. This iterative process not only generates better code but also shows good practices to other programmers.

I would really like other large software projects, such as Asterisk, to adopt it to increase the code quality and the developers interaction.

I worked a lot on rforth1 lately, a Forth compiler targetting the PIC 18f family of microcontrollers. I have added many new optimizations in order to generate smaller and more efficient code.

Let's take an example. The Forth code below cycles through the 8 possible states of 3 leds connected to ports B5, B6 and B7 of a PIC:

\\ Define three words led0, led1 and led2 designating the leds

LATB 5 bit led0
LATB 6 bit led1
LATB 7 bit led2

\\ Use timer 0 to wait for 100ms (with a 40MHz crystal)

: tmr0-init ( -- ) $84 T0CON c! ;    \\ Enable timer, 16 bits, prescaler = 32
: 100ms ( -- ) -31250 TMR0L ! TMR0IF bit-clr begin TMR0IF bit-set? until ;

\\ Move leds -- when led0 goes to 0, switch led1. When led1 goes to 0, do
\\ the same thing with led2

: leds-init ( -- ) 0 LATB c! $1F TRISB c! ;   \\ B5, B6 and B7 are outputs
: switch-led2 ( -- ) led2 bit-toggle ;
: switch-led1 ( -- ) led1 bit-toggle led1 bit-clr? if switch-led2 then ;
: switch-led0 ( -- ) led0 bit-toggle led0 bit-clr? if switch-led1 then ;

\\ Loop indefinitely with a pause between each led change

: mainloop ( -- ) begin switch-led0 100ms again ;

\\ Main program: initialize the timer and the leds then run the main loop

: main ( -- ) tmr0-init leds-init mainloop ;

Here is the assembly code with the default compiler switches: (in order to keep it relatively short, I've omitted the declaration of constants such as LATB, which are included automatically, as well as the assembly file header)

; main: defined at example.fs:26
main
        call tmr0_init
        call leds_init

; mainloop: defined at example.fs:22
mainloop
        call switch_led0
        call _100ms
        bra mainloop

; switch-led0: defined at example.fs:18
switch_led0
        btg LATB,5,0
        btfsc LATB,5,0
        return

; switch-led1: defined at example.fs:17
switch_led1
        btg LATB,6,0
        btfsc LATB,6,0
        return

; switch-led2: defined at example.fs:16
switch_led2
        btg LATB,7,0
        return

; tmr0-init: defined at example.fs:9
tmr0_init
        movlw 0x84
        movwf T0CON,0
        return

; 100ms: defined at example.fs:10
_100ms
        movlw LOW(-31250)
        movwf TMR0L,0
        movlw HIGH(-31250)
        movwf (TMR0L+1),0
        bcf INTCON,2,0
_lbl___197
        btfsc INTCON,2,0
        return
        bra _lbl___197

; leds-init: defined at example.fs:15
leds_init
        clrf LATB,0
        movlw 0x1f
        movwf TRISB,0
        return
END

The assembly code is almost a one-to-one mapping to the Forth one. However, you may notice that the compiler chose to reorder the various parts so that fallbacks can be used between Forth words. For example, switch-led0 potentially falls back through switch-led1 because of the btfsc (test one bit and skip next instruction [return in this case] if bit is clear).

However, here we have not used a nice feature of rforth1 which is the automatic inlining of words if the generated code is either smaller or more efficient. With the automatic inlining turned on, we now get:

; main: defined at example.fs:26
main
        movlw 0x84
        movwf T0CON,0
        clrf LATB,0
        movlw 0x1f
        movwf TRISB,0
_lbl___219
        btg LATB,5,0
        btfsc LATB,5,0
        bra _lbl___220
        btg LATB,6,0
        btfss LATB,6,0
        btg LATB,7,0
_lbl___220
        movlw LOW(-31250)
        movwf TMR0L,0
        movlw HIGH(-31250)
        movwf (TMR0L+1),0
        bcf INTCON,2,0
_lbl___222
        btfsc INTCON,2,0
        bra _lbl___219
        bra _lbl___222
END

Isn't that nice? You can identify the various parts of the code: between main and _lbl___219, you get the timer and ports initialization. Between _lbl___219 and _lbl___220 is the whole logic of led switching. Between _lbl___220 and _lbl___222, the timer is reset in order to wait for 100ms, and the last three lines loop until the timer fires and then goes back to the led switching logic.

If you want to try rforth1, get it here, it is free and distributed under the GNU General Public Licence version 2. At this time, it has no documentation at all but comes with several examples that you can use as a template. And people who can understand French can read this tutorial written by one of the rforth1 users.

When I laugh at this joke while I’ve seen it at least a dozen times already, I wonder if I’m not a little bit geeky.

The ICFP contest of this year starts with the implementation of a virtual machine. While I didn’t participate to the contest itself, I wrote one in Python and rewrote another one in Ada for performance reasons. Here is its code, released in the public domain.

The Unchecked_Conversion may look ugly, but they are the best way to get good performances out of the virtual machine. The code (155 lines including the header) shows how easy it is to write such a virtual machine in Ada.

This program has been written for a 32 bits machine, and should be endianness-agnostic.

--  ICFP Programming Contest 2006 -- Virtual Machine
--  Written by Samuel Tardieu <sam@rfc1149.net>, public domain
--  To compile: gnatmake -O3 -gnatp -fomit-frame-pointer vm
--  To run: ./vm codex.umz

with Ada.Command_Line;           use Ada.Command_Line;
with Ada.Streams.Stream_IO;      use Ada.Streams.Stream_IO;
with Ada.Text_IO;                use Ada.Text_IO;
with Ada.Unchecked_Conversion;
with Ada.Unchecked_Deallocation;
with Interfaces;                 use Interfaces;

procedure VM is

   type Arr is array (Unsigned_32 range <>) of Unsigned_32;
   type Arr_Access is access Arr;
   for Arr_Access'Size use 32;

   procedure Free is
      new Ada.Unchecked_Deallocation (Arr, Arr_Access);

   function To_Unsigned_32 is
      new Ada.Unchecked_Conversion (Arr_Access, Unsigned_32);

   function To_Access is
      new Ada.Unchecked_Conversion (Unsigned_32, Arr_Access);

   Mem0 : Arr_Access;

   Regs : array (Unsigned_32'(0) .. 7) of Unsigned_32 := (others => 0);

   PC : Unsigned_32 := 0;

   End_Of_Program : exception;
   Unknown_Opcode : exception;

   procedure Interpret_Opcode is
      Opcode     : constant Unsigned_32 := Mem0 (PC);
      Operator   : constant Unsigned_32 := Opcode / (2**28);
      A          : constant Unsigned_32 := (Opcode / 64) and 7;
      B          : constant Unsigned_32 := (Opcode / 8) and 7;
      C          : constant Unsigned_32 := Opcode and 7;
      Current_PC : constant Unsigned_32 := PC;
   begin
      if PC <= Mem0'Last then
         PC := PC + 1;
      end if;
      case Operator is
         when 0 =>
            if Regs (C) /= 0 then
               Regs (A) := Regs (B);
            end if;
         when 1 =>
            declare
               Base : constant Arr_Access := To_Access (Regs (B));
            begin
               if Base = null then
                  Regs (A) := Mem0 (Regs (C));
               else
                  Regs (A) := Base (Regs (C));
               end if;
            end;
         when 2 =>
            declare
               Base : constant Arr_Access := To_Access (Regs (A));
            begin
               if Base = null then
                  Mem0 (Regs (B)) := Regs (C);
               else
                  Base (Regs (B)) := Regs (C);
               end if;
            end;
         when 3 =>
            Regs (A) := Regs (B) + Regs (C);
         when 4 =>
            Regs (A) := Regs (B) * Regs (C);
         when 5 =>
            Regs (A) := Regs (B) / Regs (C);
         when 6 =>
            Regs (A) := not (Regs (B) and Regs (C));
         when 7 =>
            raise End_Of_Program;
         when 8 =>
            declare
               Last : Unsigned_32;
            begin
               if Regs (C) = 0 then
                  Last := 0;
               else
                  Last := Regs (C) - 1;
               end if;
               Regs (B) := To_Unsigned_32 (new Arr'(0 .. Last => 0));
            end;
         when 9 =>
            declare
               Base : Arr_Access := To_Access (Regs (C));
            begin
               Free (Base);
            end;
         when 10 =>
            Put (Character'Val (Regs (C)));
            Flush;
         when 11 =>
            declare
               X : Character;
            begin
               Get_Immediate (X);
               Put (X);
               Flush;
               Regs (C) := Character'Pos (X);
            end;
         when 12 =>
            declare
               Base : constant Arr_Access := To_Access (Regs (B));
            begin
               if Regs (B) /= 0 then
                  Free (Mem0);
                  Mem0 := new Arr'(Base.all);
               end if;
               PC := Regs (C);
            end;
         when 13 =>
            Regs ((Opcode / 2**25) and 7) := Opcode and (2**25 - 1);
         when others =>
            raise Unknown_Opcode;
      end case;
   end Interpret_Opcode;

   procedure Load is
      use Ada.Streams, Ada.Streams.Stream_IO;
      F : Ada.Streams.Stream_IO.File_Type;
      S : Stream_Element_Array (1 .. 4);
      L : Stream_Element_Offset;
   begin
      Open (F, In_File, Argument (1));
      Mem0 := new Arr (0 .. Unsigned_32 (Size (F)) / 4 - 1);
      for I in Mem0'Range loop
         Read (F, S, L);
         Mem0 (I) := Unsigned_32 (S (1)) * 2**24 +
           Unsigned_32 (S (2)) * 2**16 +
           Unsigned_32 (S (3)) * 2**8 +
           Unsigned_32 (S (4));
      end loop;
      Close (F);
   end Load;

begin
   Load;
   loop
      Interpret_Opcode;
   end loop;
exception
   when End_Of_Program =>
      null;
end VM;

As a member of the Areabot association, I participated to the 2006 French robotics competition last week. We had to develop specific software for our robot, driven by two Shix boards containing each one a SH7750R processor at 240MHz running Linux and a Stratix EP1S25 FPGA.

We decided to use Mercurial from the beginning for our main repository. We set up a central repository where the eight active developers could push their changes using a SSH key. Most of the users could not log into the machine as it was shared with industrial projects; they only had access to Mercurial under a shared uid.

Six users were new to Mercurial. Most of them never had used any distributed revision control system before, and some of them had never even used CVS. The basic operations (clone, pull, update and push) were easily learnt, but the first merges seemed to look like black magic to them. After a quick explanation, they were able to handle conflicts and avoid them whenever possible.

When we arrived at the contest site, we lost the connection to the central repository as no Internet access was possible there. However, most developers had a checked out copy of the repository on their laptops. We set up a small LAN and continued to write code on our laptops. Being able to serve our changes using Mercurial's integrated server was a real pleasure. We only had to ensure that each one of us had a hg serve running, and we continuously pulled changes from one repository to another.

In one occasion, we were unable to setup a LAN between the two laptops we were using and needed to transfer the latest changes from one of them to the other. Rather than copying the raw files to an USB key, we created a Mercurial repository on it, pushed to the repository from the up-to-date laptop and then pulled from it from the other laptop. This way, no files were ever exchanged outside the revision control system and this didn't take any extra time to do so.

So to make it short: Mercurial was a real help for our development, both in connected (central repository) and disconnected (peer-to-peer) modes. Having a full access to the whole history was very valuable.

Some figures:

• Number of active developers: 8
• Time span: two months
• Lines of code written for the competition: 30617 (3503 lines of C, mostly Linux device drivers, 12542 lines of Ada, 357 lines of Makefile, 14215 of Verilog for the FPGA, some of them being shared with other projects using the same board)
• Number of commits: 700 (including 89 made while on the contest site)

For the 2006 French robotics cup, I wrote two utility packages for GNAT, the GNU Ada compiler:

• areadline: access the readline library from Ada;
• aforth: embeddable Forth interpreter written in Ada (uses the areadline library).

I haven’t put a license file in them yet, but you can get them under the GNU General Public License version 2.

As a low-level software guy, I often have to work with electrical engineers to build custom hardware and software systems. I am constantly amazed by the tricks necessary to make the hardware part work and the experience needed to build reliable electrical components. I decided to apply the same techniques to my software.

First of all, I have noticed that electrical engineers often use ground planes on their boards. A ground plane is just a large area connected to the ground. This reduces the crosstalk effect, where the signal on two wires located near to each other may influence each other.

I did the same thing in my C programs. I have inserted large areas of zeroes between my functions:

    int f (...)
    {
       ...
    }

    char _ground_plane_1[1024] = {0};

    int g (...)
    {
       ...
    }

    char _ground_plane_2[1024] = {0};

    int h (...)
    {
       ...
    }

The second important thing was about metastability. In a FPGA (an electronic device that you can customize so that it does what you want in hardware, to make it short), if you sample a signal while it is going from GND to Vcc and store it in a register, the register may take a value of Vcc/2 (I've seen this happen when sampling the input of a digital video camera). This value will be propagated and will eventually be resolved after passing through some gates into either GND or Vcc. The problem is that it may be resolved into different values at different places. To avoid this problem, you insert intermediate registers between the sampling of the signal and its propagation in the FPGA. There is a good chance that you get GND or Vcc after the first register. A better chance after the second one. A very good chance after the third one.

So in my code, I changed every assignment from a function result from:

   int a = f (x, y);

into

   int _a0 = f (x, y);
   int _a1 = _a0;
   int _a2 = _a1;
   int a   = _a2;

I ran my test programs and noticed that they were much more stable than before! I encourage everyone to do the same thing, in every programming language.

We have so much to learn from electrical engineering...

Before leaving for my vacation,here are two small Python libraries I wrote that may help you if you want to participate to Project Euler:

• primes.py: fast prime number generation and integer factorization
• pell.py: find solutions pairs to Pell diophantine equation x²-Dy²=1

This may come as a surprise, but I will today write about a programming language for which no Free Software implementation exists, the J programming language. J does not stand for the J dirty word (Java), but is the full name of the language.

I first heard about J while solving some problems on the Project Euler challenge. One of the problems to be solved was "given that C(n,p) is the number of ways to take p items amongst m items, find the number of C(n,p) greater than one million for n between 1 and 100 inclusive."

This was a very easy problem. I coded my solution using Python and, by curiosity, looked at how other people did it. I saw someone mentionning its J solution:

+/1e6<,!/~>:i.100

Wow, 17 characters! As I was in disbelief, I gave it a try and installed a copy of J on my GNU/Linux laptop. I cut and pasted the expression, and it gave me 4075, the expected solution. Let me describe how it works.

First of all, expressions are evaluated from right to left.

i.100

will generate a list of all integers from 0 to 99 (the 100 first non-negative integers). Then, the increment operator is used, so the part

>:i.100

leads to the list of numbers from 1 to 100. The rank of the increment operator is zero, which means that it operates on individual items, not on lists. Since we give it a list as argument, each member of the list will be incremented, and give the new 1 to 100 list.

The C(n,p) operator in J is written as

p ! n

However, we want to apply it for every p and n in 1 to 100. The tilde (~) modifier means that we want the left argument of the ! function to be the same as the right argument. The slash (/) modifier means that we want to build a table. Without it, the ! operator would be applied to the first item of the left argument and the first item of the right argument, then to the second item of the left argument and the second item of the right argument and so on. Here, it is applied to every combination of its left and right arguments, meaning that the result is a 100x100 table:

!/~>:i.100

Now, the coma (,) transforms the 100x100 table into a 10000 elements flat list:

,!/~>:i.100

Now, we want to select all the elements greater than one million. For that, we will compare each element to 1e6 (one million in scientific notation). Since the left argument is a plain number and the right argument is a list (the 10000 long list we obtained), the result will be a 10000 items list containing either 0 (false) or 1 (true):

1e6<,!/~>:i.100

Ok, so we now have a 10000 items list containing 0 (smaller than one million) or one (greater than one million). To find out the number of ones, we only have to sum up the items. Using the plus (+) operator and the slash (/) modifier, an addition will be inserted between every item of the list:

+/1e6<,!/~>:i.100

That's it.

To the computer literate people, it looks a lot like APL without the special characters and the need for a special keyboard. No surprise, J and APL have both been designed by Kenneth E. Iverson.

J is very efficient while working on large sets of data. Its table operator and its rank analysis almost entirely obviates the need for explicit loops. For example, if you want to multiply the 100 first prime numbers, you can use the p: operator which returns the n-th prime number (starting with 0, which returns 2, 1 returns 3, 2 returns 5, 3 returns 7 and so on):

*/p:i.100x

The x modifier stands for extended (read unlimited) integer precision. You want to know what the solution is? Install your copy of J and try it yourself.

When doing some heavy 3D rendering with Blender, I realized that one of my animation was going to take 53 hours to render. Existing distributed rendering systems such as DrQueue were fine but require that some software other than Blender or basic interpreters (such as Python or Perl) is installed on the contributing machines.

So I wrote a simple Python script called blenderdist.py which only needs blender and python to run. A server is launched with:

% python blenderdist.py --server PORT JOBDIR RENDERDIR

and will monitor the status of job files (three lines each, the blender file, the first frame to render and the last one to render) in JOBDIR. Resulting frames are placed under RENDERDIR/jobname. Job names have to end with .job and if a file named JOBNAME.job.suspend is present, its rendering is suspended to allow urgent jobs to be rendered first.

Clients are launched with:

% python blenderdist.py --client HOST PORT

The server constantly monitors its source code. Whenever the Python script changes, the server relaunches itself (without loosing its state saved in a checkpoint file) and the next time the clients connect to it they will receive the new version of the program and relaunch themselves too.

I have currently a dozen machines working as I type, most of them out of my control. Some friends of mine have agreed to run the script and are contributing CPU cycles for my rendering. This proves to be very helpful. The program is much less powerful than generic ones such as DrQueue, but it does not require that disk space is shared between machines or setting up complex scripts. It just gets the job done.

Note: as this script has been written for a one-time shot need, I place it under the public domain, do whatever you want with it.

Getting blenderdist

You can get the current development version of blenderdist using git:

git clone git://github.com/samueltardieu/blenderdist.git

This will create a blenderdist directory in which you will be able to record your own changes.

You can also browse the blenderdist repository on GitHub.

Contributing to blenderdist

Reporting bugs and asking for features

If you find a bug or have an idea for a new feature, you might consider adding a new issue. The more precise you will be in your description, the more useful it will be.

Submitting patches

Patches are gladly accepted from their original author. Along with any patches, please state that the patch is your original work and that you license the work to the blenderdist project under a license compatible with the current one (public domain license).

To propose a patch, you may fork blenderdist repository on GitHub, and issue a pull request. You may also send patches and pull requests by email.

I always tell my compilation class students that there are two steps to follow when developping a new program:

1. The program must accept any valid input and produce accurate results. The result of feeding the program with invalid input is undefined, it can either crash or silently produce wrong results.

2. The program must reject any invalid input.

I see too many programmers try to implement the second phase before finishing the first one. It is true that implementing only the first one adds a burden onto the user, as he must provide valid input. But when the user makes no mistake, the program won't either. However, as weird as it may seem, the second step is often the most difficult to achieve.

I feel quite ashamed of the pun on the name and the logo of my new Forth compiler…