Friday, July 18, 2008

Quote of the Day

We just wrapped up the Advanced Mathematica Summer School, two weeks of lectures and on-site consulting and coaching for attendees in developing a Mathematica project idea. As a developer, this was an awesome opportunity to work hands-on with real users and develop a better feeling for (1) real world problems, and (2) ways that people use our products, versus what we may assume they want and what they know.

During the lightning presentations this morning, one attendee wanted to express his appreciation:

"I want to thank Wictor for writing some really cool code for me,
and I want to thank Paul-Jean for helping me understand the code that Wiktor wrote."

Wednesday, July 16, 2008

Yes We Controlled A Rover

I'm just recovering from this weekend's ICFP Programming Contest in which we had to write a controller for a simulated Mars Rover. I'm pretty sure we're not winning anything, even assuming we ever get Mathematica in the hands of the contest organizers. After the rules were announced the week before, I frantically went around trying to figure out if we could even enter a contest with Mathematica, a commercial product that requires a license key to run, finally coming up with two workable options. Only to discover on Saturday that one of the options wasn't going to work because the submission form was capped at 20MB. I had counted on being able to upload a stripped down copy of Mathematica weighing in at around 140MB. The contest staffer on the IRC chat channel told me we would work it out later.

We used Java to do the socket stuff, and JLink to go between Java and Mathematica. This isn't as hard as it might sound, and especially as all three of us on the team develop Java/Mathematica hybrid products (Wolfram Workbench is Eclipse-based and webMathematica works with Tomcat).

The code we worked on during the contest had Java in control and called Mathematica to process each event from the server (i.e. the rover). This worked fine, but I wish I'd listened more carefully to the 3 senior people at work who advised Mathematica be in control and call Java.

Last night I inverted the control and rewrote the little event loop in Mathematica, and suddenly the light went on that we really missed out by not having the Mathematica front end part of our interactive development process. I was quickly able to write a Dynamic-based dashboard: literally we could watch the controller's state updated in real time, including calculated state. We saw things like instantaneous speed, heading, and the rover's steering and acceleration state. It seems it would have been so much more helpful to see these numbers as our rover wandered around, to get more familiar with the problem. As it was we stared at static log files of telemetry messages after the run was over.

I hope I can write a little more about our experience later. It was fun though.

Wednesday, June 25, 2008

Replacing One Line with Two in Eclipse

Eclipse 3.4 is out today. In reading through the list of new features, I find one that I literally could have used yesterday.

Simply, I was doing a refactoring where I wanted to replace one import declaration by two, so my desired replacement text was two lines. Eclipse has a nice multi-file search/replace feature. However, I couldn't find or figure out if the replace text field would accept some syntax to indicate "I want a line break here." Trying the obvious \n resulted in a literal backslash-n.

In Eclipse 3.4, we can now use \R to indicate a platform-dependent line break, and \n and \r now work as expected. Usually I hate being on the bleeding edge, but this time I curse my reluctance to have been trying out the release candidates.

Tuesday, June 17, 2008


In relation to the release of Firefox 3.0, someone at work mentioned that we have screencasts too, and I was happy to see one where Theo shows off Luc Berthelet's version of Breakout. Theo scrolls through the code on the screencast, so by judicious pausing you can probably copy it, but I wish I could find the notebook somewhere, for, you know, research purposes.

In a serendipitous connection, Wikipedia tipped me off that in the past month or so Luc has broken out of his position at Electronic Arts to start Tir Nua, something in the virtual world line of goods. One of his new employees that he brought with him is a name familiar around my workplace, former Wolfram Research employee Sarah Flannery. I remember hearing Sarah give a talk last fall about the webMathematica-based Wiki she'd worked up for Sims Online players, and how she'd tackled the runaway inflation in the Sims Online economy (all sources and no sinks).

People like Luc and Sarah are fun users for Wolfram employees like me who consider themselves mainline software designers and like to see Mathematica applied more like a regular programming language in areas very different from what you might typically expect.

Wednesday, June 04, 2008

Picking a CLOS Implementation to Play With

Being provoked into trying to learn a bit more about CLOS's method of multiple dispatch, and wanting to find an implementation, led me on this search path in a few spare minutes:

1. Search Google for CLOS

2. Click, which is on the site of Richard Gabriel ("worse is better")

3. Click the intriguing title CLOS: Integrating Object-Oriented and Functional Programming

4. Read with interest on the first page the essence of multi methods:

A generic function, or polymorphic function as it is sometimes called, is one whose implementation depends on the types of its arguments. That is, the code that is executed for a particular set of arguments is mechanically determined by the types of the arguments.

In strictly functional languages, an operation is defined by a single, monolithic piece of code; any argument-type conditionality is expressed as code explicitly programmed in by the user. In contrast, the CLOS notion of generic functions supports automatic selection from among separately defined, typespecific implementational parts. Yet, from the client’s point of view, generic functions and traditional ordinary functions are called in the same way: The procedural abstraction barrier is still in force.

5. Start looking for implementations. Search reddit for "lisp implementations".

6. Click Common Lisp Implementations: A Survey.

7. The survey lists 11 Common Lisp implementations. Of these, only 5 are listed as available on the Unixes and Windows. Of those, only 3 do not have commercial licenses. Two of the remaining choices have weird names: Armed Bear Common Lisp, which does not look promising (its own home page says, under "Bugs", that "ABCL's CLOS is intolerably slow"), and Embedded Common Lisp (ECL). It's difficult to tell what immediately from Wikipedia or Google what kind of support has. But the remaining candidate, GNU clisp, appears to be in good standing, judging from the Wikipedia article (where it is claimed this is the platform Paul Graham used for Viaweb), and the Sourceforge stats which claim 100 downloads a day in the past week.

8. Find the Clisp site. Another Lisp site without an obvious Download link.

Friday, May 30, 2008

Multiple Definitions

We had an interesting discussion at work yesterday debating whether Mathematica supports multimethods with its variety of pattern-matching. So I'm taking the opportunity to do a mini-survey of the multiple dispatch spectrum, starting with overloading. As far as Mathematica, it clearly gives you the power of selecting from multiple definitions based on runtime information; more on this in a minute.

Overloading allows you to write different definitions of a function or method, and the definition used when you call the function depends on the number and types of the arguments you pass them. That is, the overload resolution is done by the compiler at compile time with static type analysis. Whatever type your arguments are, and exactly those types, will determine which definition is chosen.

Multimethods let you write different definitions of a function or method, and the definition used when you call the function depends on the number and types of the arguments you pass to them, as examined at runtime. Now you can write one definition for a class, and specializations for its subclasses if so desired, and the definition will be chosen based on the actual type of the arguments at runtime.

You get into a fuzzy gray third area if the runtime values can also be used to select different definitions. This is where Mathematica lies, because its pattern matches can be used to differentiate between a list of at least one element and a list of at least two elements, or between the symbols Null and Infinity. What's useful for writing symbolic algorithms turns out to be useful for regular programmers.

It seems that ML's structural pattern matching is also in this fuzzy gray third area, and that helps me make an interesting connection. For my purposes, multiple dispatch is interesting because it's the way to do expression tree traversal. That is, it lets you write pretty printers and type checkers and the like without needing to code the dispatch yourself (if the node is actually a lambda abstraction, do this, but if it's a cons cell, do that). What I'm noticing now is that one way or another, multimethods and pattern matching are giving you the notational convenience that I enjoy in writing tree traversals, with still perhaps an edge to pattern matching on that score.

Wednesday, May 28, 2008

The ucc Compiler

Someone with the name dreamAnders has posted announcements to comp.compilers and comp.lang.c for his small open-source C compiler, ucc, the chief attraction of which is that the source code is meant to be small and self-explanatory.

Wednesday, May 21, 2008

On "I can't believe I'm praising Tcl"

Today we look at a refreshing use case for a programming language, where economy of expression in calling functions from a read-eval-print loop is prized. Raganwald recently tagged "I can't believe I'm praising TCL", in which the embedded systems author helped us understand how TCL made for a great debugger command environment, and the "pop infix languages (C/Java/Python/Ruby/you name it)" don't.

In this case the author wants to define some glue function or functions, and then in the language's interactive interpreter, call his function over and over. He's not programming; he's commanding, so the function calls need to be short and sweet, so he doesn't mind typing them for hour after hour as he thinks about the real problem, a buggy piece of embedded hardware. The author wants a command shell, where he uses his command interface to an embedded device as a kind of gdb replacement. An example session to set breakpoints, inspect memory, etc., looks like this:

$ pmem 0 stat
$ pmem 0 bkpt 0 0xbff
$ pmem 0 bkpt 1 0xa57
$ pmem 0 cmd run
$ pmem 0 stat
$ pmem 0 pc
$ pmem 0 rstack
3 return addresses
addr 0: 0x0005
addr 1: 0x05a8
addr 2: 0x0766
$ pmem 0 cmd stp
$ pmem 0 pc
The question then is whether a language you may be designing or using could support something close to this syntactic economy for calling functions.

The argument for Tcl over the pop infix language may perhaps be best summarized by this quote:
And then we have interactive shells. And in Python it’s doit("xx","yy"). And in Lisp it’s (doit "xx" "yy"), or (doit :xx :yy), or (doit xx yy) if you make it a macro. And in Ruby it’s doit :xx :yy, if you use symbols and omit parens. And that’s about as good as you can get without using your own parser as in doit "xx yy", which can suck in the (more rare) case when you do need to evaluate expressions before passing parameters, and doesn’t completely remove overhead. Also note how all these languages use (), which makes you press Shift, instead of [] which doesn’t. Ruby and Perl let you omit (), but it costs in readability. And [] is unanimously reserved for less important stuff than function calls.


First we see the emphasis is not on defining functions, on programming, but on using, on the syntax for calling, functions. The author wants an internal DSL (Domain Specific Language).

Second, it should be noted that in discussing () that Scheme lets you use [] as well as (). There's good Scheme style, where [] is reserved for the let blocks, but if you open up Dr. Scheme or Chez Scheme, define some choice Turtle graphics functions, and start typing commands like [penup] [rt 45] [pendown] [fd 100] it will work fine.

One thing the author noted is that TCL's preference for strings over variables makes bkpt a string and $bkpt a variable, whereas in the pop infix languages, it's the variables that get lexical economy and strings that need delimiters. Because of this preference, calling a Tcl command lets you pass in what look like symbols, but you treat them as strings in the command definition. Hence, for the author's use case, a chief consideration seemed to be a way to write symbolic arguments, where the command in question may take a one-of-several subcommand or option name, without lexical decoration like string delimiters or single quotes or colons. I wonder if this was really a language design goal of Tcl, because it's hard to understand the motivation for the string-vs-variable syntax any other way. For all that, enumerated types or sum types are a known language feature that meet the author's criterion. In Standard ML you could define a datatype Subcommand = bkpt | status | memset or the like, and now undecorated references like bkpt can appear as arguments.

Note if you do define your functions as Scheme macros, to address the symbol/string problem, and if you modified Scheme to accept an S-expression forest on each line (i.e. no need to delimit a top-level input line with parens), you'd have the economic expression of Tcl. I think this is worth considering in some circles where Scheme may be more familiar.


This could be a nice motify for the "language design of the day": extend the basic Scheme-like interpreter to support an extensible debugger command interface.

Friday, May 16, 2008

Call by Need Lambda a Poor Man's Macro?

I've been seriously considering why more languages don't include a call-by-need lambda (hereafter called "lazy lambda"). With its delayed evaluation it offers macro-like powers for writing non-looping forms (they're bad for loop forms since the arguments are evaluated but once by design), but they don't have the bloating effect of macro expansion (if code size is more important to you than the time overhead of a function call), and they are hygienic. They're not a cure-all, but this seems to be an approach which can still be wielded effectively by trained professionals.

How to Use Lazy Lambda

Here's how a lazy lambda would work in an existing language like Scheme. You have a new abstraction lazy-lambda with precisely the same syntax as lambda. When applied, lazy-lambda follows call by need evaluation rules. That means arguments to the lazy procedure are not evaluated at the call site, but only when their corresponding formal parameter is first referenced inside the body. On this reference, the evaluated argument value is remembered for future references inside the body. Here's how you might write something like Groovy's Elvis operator:

(define ?: (lazy-lambda (expr default)
(if (null? expr) default expr)))
The thing I like is that this is automatically hygienic: it works fine even if you call it in an environment with variables named expr or default.


I like to divide my thinking about new features into two phases: introduction and use. When lazy-lambda is introduced, the parser needs to create a structure essentially identical to that of a lambda, namely an arguments list and a body expression, but of course it needs to be marked as a different type from lambda so the evaluator can distinguish the two. Lazy lambda is used in two ways, once when it is evaluated (e.g. when a lazy-lambda expression is returned from a function) and once when it is applied.

Summary of Lazy Lambda Implementation
Introduction: '(lazy-lambda args body)
Evaluation: '(closure (lazy-lambda args body) env)
Application: Bind args to thunks, evaluate thunks in a memoizing way

When lazy-lambda is evaluated, it should create a closure, the pair of the lazy-lambda expression and the environment in which it was evaluated. This closure needs to be marked as a different type from a regular closure. Alternatively the evaluator can be arranged to check the type of the "lambda" expression: a closure may look like '(closure (lambda args body) env) or '(closure (lazy-lambda args body) env).

What happens a lazy-lambda closure is applied? We know you don't evaluate the arguments, but what then? As with eager closures, you first create a new environment scope. Then, instead of binding the formal arguments to the evaluated values of the arguments, you bind the formal arguments to some box (container) of the unevaluated argument expressions. The container needs to be distinct from any other language type so that the evaluator knows how to treat it. That is, once we set up the new environment scope, we will simply evaluate the body of the lazy-lambda under this new environment, and the references to the formal arguments need to be handled in this special memoizing way. So let's introduce an expression type delayed, which is not directly creatable in the language, and we bind each formal argument x with actual argument expression A to the "value" (delayed A env). The env value will be needed when we evaluate A, because we will need to evaluate it in the calling environment, not whatever environment is in effect when the symbol is first referenced. (Think about what gets returned by (lambda (x) ((lazy-lambda (x) (begin (set! x (+1 x)) x))) x).) Then when the evaluator handles variable references and gets a delayed value back from the environment lookup, it's time to do the memoizing: evaluate A in environment env, rebind (set!) the referenced variable with its evaluated value, and return that.


None of the popular scripting languages I can think of (Javascript, Perl, Python, Ruby) have a macro facility, but most of them have anonymous functions which evaluate to closures in the Scheme sense. On the other hand, they also tend to have a richer set of control structures (Perl's unless), and they have other mechanisms (dare I say classes and objects?) which address most of the killer applications for macros, and hence for lazy-lambda. But for all that, I'd have to figure that those languages, and the tinier languages or DSLs, could add this feature.

Macros are subtle things to get right, and I'm sure there are deficiencies I haven't addressed here. But that shouldn't stop us from thinking about these issues, and I think there's some potential value in the call by need lambda.

Wednesday, May 14, 2008

Thoughts on an S-Expression Parser

In this post we look at a tiny Scheme parser, and generalize it to a non-language-specific S-expression parser that can be subclassed to handle any language design, as a base class for studying language varieties.

As I mentioned last time, I recently wrote a tiny Schemish interpreter, and then started extracting from it a basic interpreter platform that other people or myself could use to try out different language designs or implementations. One practical goal would be for instructors to provide the framework and have students modify it. The approach is not mine, it's from Sam Kamin's "Programming Languages: An Interpreter-Based Approach" (1990).

The original Schemish parser had these two parsing methods:

protected Expr parseExpr() throws ParseError
Token token = consumeToken();
case '"': return new StringLit(token.text);
case '(': return parseExprList(token);
// Test the token to see if it's a numeric
Int intExpr = Int.fromString(token.text);
if(intExpr == null)
return new Atom(token.text);
return intExpr;

protected Expr parseExprList(Token openParen) throws ParseError
Vector acc = new Vector();
while(peekToken().type != ')')
Expr expr = parseExpr();
Token closeParen = consumeToken();

// Handle special forms
ExprList retval = null;
if(acc.size() > 0 && ((Expr)acc.firstElement()).isAtom())
Expr head = (Expr)acc.firstElement();
String headName = head.getAtom().getText();
String lambdaUsage = "Syntax error: "+
"expected ("+headName+" (arg ...) body)";
if(acc.size() != 3)
throwError(openParen, lambdaUsage);
Expr argExpr = (Expr)acc.get(1);
throwError(openParen, lambdaUsage);
ExprList argList = (ExprList)argExpr;
Expr[] args = argList.getElements();
HashSet argSet = new HashSet(); // to check for duplicates
for(int i=0; i < args.length; ++i)
throwError(openParen, lambdaUsage);
boolean wasAdded = argSet.add(args[i]);
throwError(openParen, "Syntax error: argument "+
args[i].getAtom()+" appears more than once");
Expr bodyExpr = (Expr)acc.get(2);
retval = Lambda(argList, bodyExpr);

if(retval == null)
retval = new ExprList(acc);

retval.filename = m_filename;
retval.firstLine = openParen.line;
retval.lastLine = closeParen.line;
return retval;

The lambda-handling code is big, and obscures the structure of the list parsing part. That may not be so bad if you're working on this one interpreter, you don't forget the basic list-parsing structure, because it's simple. You'll care more about all the special forms. But for my purposes, of wanting to write many interpreters from the same code base, we want to be able to talk about different interpreters, and it's a little awkward: you're always sharing code patches, and having to explain where they go. Instead, why not give a sufficient base class, and share complete subclasses?

The improvement gives a parser class which handles only S-expressions; it knows only atoms and expression lists, it doesn't know any language constructs at all: it knows no keywords. You can think of it as generating just a tree structure, like an XML parser. Parsers for a particular language design will be written as subclasses, and will override the methods constructAtom and constructExprList. These methods are reminiscent of the actions in YACC-like parser generators, the blocks of code that construct parse tree elements given data named by the grammar rule symbols and from the general lexer and parser state (e.g. line numbers in our case).

Thus, parseExpr and parseExprList reduce to tiny fragments and subclasses can flesh out the meat of special forms in constructExprList:

public Expr parseExpr() throws ParseException
Token token = consumeToken();
Expr retval = (token.type == '(')?
: constructAtom(token);
return retval;

protected Expr parseExprList(Token openParen)
throws ParseException
Vector acc = new Vector();
while(peekToken().type != ')')
Expr element = parseExpr();
Token closeParen = consumeToken();

Expr retval = constructExprList(acc, m_filename,
openParen.line, closeParen.line);
return retval;

protected Expr constructAtom(Token token)
return new Atom(token.text);

protected Expr constructExprList(
AbstractCollection exprs, String srcId,
int startLine, int endLine)
ExprList retval = new ExprList(exprs);
retval.filename = srcId;
retval.firstLine = startLine;
retval.lastLine = endLine;
return retval;

Now the Schemish interpreter can subclass Parser and call it SchemeParser, overriding constructExprList to handle special syntactic forms, and overriding constructAtom to handle language-specific literals, such as character literals or rational number literals (2/3).

Friday, May 09, 2008

Thoughts and Code for the S-Expression Lexer

My recent project has been a tiny Schemish interpreter, and more recently have been considering a design that would work well as the Java counterpart to Kamin's chapter 1 interpreter, a calculator language using Lisp syntax, which is to be morphed into any one of a variety of different languages based on S-expression syntax.

So, this post is just for sharing some observations in working on the lexical analyzer part, as well as its code.

Just so it's abundantly clear, the problem a lexical analyzer solves, for S-expressions anyway, is to get a stream of parens, quotes, and symbols out of a character input source.

The apostrophe quote operator, as for creating list literals like '(lambda (x) x), appears to be a token not requiring whitespace. I've never seen the apostrophe not have preceding whitespace, but after testing MzScheme, ChezScheme and a few other minor Scheme implementations, it's apparent that a'b'c is the same as a 'b 'c. I've not done any serious development in Scheme, but I wonder whether this is common knowledge among Scheme programmers.

Similarly, Scheme read-eval-print loops appear to accept forests of S-expressions at the prompt, not just one expression. If you type 1 2 3 4 and the values get echoed back. This is useful for multiple defines, or for pasting code. Obviously, any REPL loop should support this behavior if at all possible.

I was happy to see that StreamTokenizer tracks line numbers. Having line numbers available "for free" helps error messages instantly. For what it's worth, I want my scanner to track column numbers too, but I understand if James Gosling (marked as the author of StreamTokenizer) didn't want to get into arguments about what a tab is worth.

The xUnit test frameworks are a much welcome tool for testing language processors. In 1998 I was fiddling with diff-based Perl scripts for automated regression testing. Writing JUnit tests is a lot more fun, productive, and exact than relying on textual comparison with blessed output.

Rather than subclass StreamTokenizer, I wanted to change the consumer's model of looping from "while the current token is not end-of-file" to a standard Iterator terminating on !hasNext(). This required making use of pushBack() on every token get, but I considered the ease of use for the client had a slight edge.

Using an iterator means you need an object to return, so there is a small Token class returned by the iterator. Token bundles the public fields of the StreamTokenizer that represent the token value. I opted not to have StreamTokenizer parse numbers. Since the intended use is ultimately interpreters for arbitrary languages merely based on S-expression syntax, I needed to let them have their own numeric literal syntax and domain of representation (double? float? BigInteger?). Now for some code. Token looks like this:

package jfkbits;

public class Token
public static final int SYMBOL = StreamTokenizer.TT_WORD;
public int type;
public String text;
public int line;

public Token(StreamTokenizer tzr)
this.type = tzr.ttype;
this.text = tzr.sval;
this.line = tzr.lineno();

public String toString()
case SYMBOL:
case '"':
return this.text;
return String.valueOf((char)this.type);
Here's how the type field, an int, as defined in StreamTokenizer, works: for "ordinary characters", the type is the character literal cast to an int. The LispTokenizer marks '(', ')', and the apostrophe quote operator '\'' as ordinary. In code using Token, this reads very naturally, as in if(token.type == '(') return parseExprList();. For "words", atoms in our case, the type is a negative int defined by StreamTokenizer.TT_WORD, which Token redefines as SYMBOL. If we read a Token t with t.type==Token.SYMBOL, the good stuff (like "42", "x", "eval", or "lambda") is in t.text. String literals have the type code of the delimiter, so t.type=='"' means we've got a string literal, the contents of which (without the delimiter!) are also in t.text.

And what about string literals? Strictly speaking, the same decision I made about numeric literals should also apply to string literals. Namely, that different languages have different syntaxes and potentially different representations. Perhaps I should not configure StreamTokenizer to recognize string literals. In that case, the parser would get atoms containing the double quotes, themselves, and the parser would be expected to split it apart. Currently, I don't expect this tool to be used for studying string literals very much.

And finally, for the code itself:

package jfkbits;

import java.util.Iterator;

public class LispTokenizer implements Iterator
// Instance variables have default access to allow unit tests access.
StreamTokenizer m_tokenizer;
IOException m_ioexn;

/** Constructs a tokenizer that scans input from the given string.
* @param src A string containing S-expressions.
public LispTokenizer(String src)
this(new StringReader(src));

/** Constructs a tokenizer that scans input from the given Reader.
* @param r Reader for the character input source
public LispTokenizer(Reader r)
if(r == null)
r = new StringReader("");
BufferedReader buffrdr = new BufferedReader(r);
m_tokenizer = new StreamTokenizer(buffrdr);
m_tokenizer.resetSyntax(); // We don't like the default settings

m_tokenizer.whitespaceChars(0, ' ');
m_tokenizer.wordChars(' '+1,255);

public boolean hasNext()
if(m_ioexn != null)
return false;
catch(IOException e)
m_ioexn = e;
return false;
if(m_tokenizer.ttype == StreamTokenizer.TT_EOF)
return false;
return true;

/** Return the most recently caught IOException, if any,
* @return
public IOException getIOException()
return m_ioexn;

public Token nextToken()
return (Token)next();

public Object next()
catch(IOException e)
m_ioexn = e;
return null;

Token token = new Token(m_tokenizer);
return token;

public void remove()
A token stream can be processed something like this:

LispTokenizer tzr = new LispTokenizer("(define x 42)");
for(Iterator it=tzr; it.hasNext(); ) {
Token token = it.nextToken();
And finally, some unit tests.

package jfkbits;

import java.util.Iterator;

import junit.framework.TestCase;

public class LispTokenizerTest extends TestCase
public LispTokenizerTest(String name)

public void testLispTokenizerIterator()
LispTokenizer tzr;

tzr = new LispTokenizer("");

tzr = new LispTokenizer(" ");

tzr = new LispTokenizer("\n");

tzr = new LispTokenizer("7");
checkToken(1, "7", Token.SYMBOL,;

tzr = new LispTokenizer("()");
checkToken(1, null, '(',;
checkToken(1, null, ')',;

tzr = new LispTokenizer("(newline)");
checkToken(1, null, '(',;
checkToken(1, "newline", Token.SYMBOL,;
checkToken(1, null, ')',;

private void checkToken(int line, String text, int type, Object tokenObj)
assertTrue(tokenObj instanceof Token);
Token token = (Token)tokenObj;
assertEquals(line, token.line);
if(text != null && token.type == StreamTokenizer.TT_WORD)
assertEquals(text, token.text);
assertEquals(type, token.type);

public void testCharacterMapping()
assertEquals((int)'(', mkTokenizer("(").nextToken().type);
assertEquals((int)')', mkTokenizer(")").nextToken().type);
assertEquals((int)'\'', mkTokenizer("'").nextToken().type);

assertEquals(StreamTokenizer.TT_WORD, mkTokenizer("0").nextToken().type);

public void testSimpleLispExpressions()
test("",new String[]{});
test("()",new String[]{"(",")"});
test(" ()",new String[]{"(",")"});
test("\n()",new String[]{"(",")"});
test("() ",new String[]{"(",")"});
test("()\n",new String[]{"(",")"});

public void testLispExpressionsWithComments()
test(";Comment here\n()", new String[]{"(",")"});

public void testLispExpressionsWithStrings()
test("\"\"",new String[]{""});
test("\"a\"",new String[]{"a"});
test("\" a\"",new String[]{" a"});
test("\"a \"",new String[]{"a "});
test("(print \"Hello world.\\n\");",
new String[]{"(","print","Hello world.\n",")"});

public void testFactorial()
String src =
";; Compute the factorial of a given number\n"+
"(defun fact (n)\n"+
" (if (< n 2)\n"+
" 1\n"+
" (* n (fact (- n 1)))\n"+
" )\n"+
" )\n"
String[] expected = {

static void test(String src, String[] expectedTokens)
LispTokenizer tzr = mkTokenizer(src);
int i = 0;
for(Iterator it=tzr; it.hasNext(); i++)
Token token = (Token);
assertTrue("Expected "+expectedTokens.length+" tokens, got more",
i < expectedTokens.length);
assertEquals(expectedTokens[i], token.toString());

static LispTokenizer mkTokenizer(String src)
return new LispTokenizer(src);

Wednesday, May 07, 2008

Motivations for Little Interpreters

We're continuing a series about writing little interpreters. Although it is fun and cool, so are isolated guitar licks for about the first five minutes; long-term you probably will want to play whole songs if you want to have listeners. Similarly, you need an application, killer or not, for an interpreter or it will lie around collecting bit dust and require "maintenance" (right, Dijkstra?).

I suppose you could say I'm talking about an interpreter for a Domain Specific Language here, but really all I mean is that if you care enough to write an interpreter, you may as well take the opportunity to build into it something you can use, and for this post I'll address the area of a useful domain.

Specifically, if you care about an interpreter it means it will support a domain you care about: photos, 3D graphics, matrices.

In the implementation language of the interpreter, you will want to define
1. Data structures
2. Ways to construct and operate on them

and you'll make provisions for these in your language. Thinking these through carefully, and probably writing them into a runtime library complete with unit tests, is a respectable way to approach things before sticking an interpreter front end onto the data and code of your domain of interest.

Let me give you one simple example of an interpreter I wrote for personal productivity. In 1995 I wrote "Joel's Calculator" to help me write status reports for my manager, and also to do some basic statistical analysis. (No, I didn't have Excel; I was working with an HP-UX workstation.) Our embedded systems group had gotten a rare opportunity for a complete product rewrite, and we needed to track our time and estimates carefully. We had to track time spent on particular modules and count overhead, and in our weekly status report submit an account of time on our various modules, with overhead (anything not in a particular module) evenly divided among our projects. I would keep a log of time spent that looked something like this:

Tue May 7
0840-0920 Email
0920-1135 Serial driver
1250-1300 Ovr
1300-1400 Phase 2 mtg
1400-1600 Serial driver testing
1600-1715 Code review
It was an easy way to keep track, in a text editor. Then at the end of the week, I would sum the "billable hours" for modules like Serial driver. What I ended up wanting was a way to do "time arithmetic":

serial = 11:35-9:20 + 16:00-14:00
ovr = 9:20-8:40+0:10+14:00-12:50+17:15-16:00
This worked very well for me as a workflow. I could write simple expressions like this, assign them to variables, combine the results gradually, and so on. This was really a desk calculator, but I was pleased with the effect that I could enter times textually in a very natural way, use simple infix arithmetic notation, and have it just work.

In this case my chief domain of interest was pretty simple, a pair of hour and minutes, and the operations on the domain were also fairly simple, but a little challenging to get right.

Of course, you may be coming at this from the perspective that the goal and the domain are already well defined. For example, you're working with a library of interest and you'd like to play with it interactively; you can envision making Scheme bindings and writing abstractions to make it do something useful. Or you even have a very powerful system written in an existing but limited language, but you need to bust out of the limits. Using a lightweight Lisp/Scheme interpreter that you can modify to script some macros to generate code in another language may solve some scaling problems for you.

So, if you want to start a little interpreter project, which I'd like to encourage, before you get started, pick a goal, pick a domain, and refine the domain as the first step.

Tuesday, May 06, 2008

Google AppEngine Activation Arrives

I signed up for Google AppEngine, well-covered on, about a month ago, but got the "don't email us, we'll email you" message at that time. Today I got my email letting me know I can start farming on the Google spread.

Friday, May 02, 2008

Little Lisps: Programming Candy or Spinach?

Last time (StreamTokenizer and Declarative Lexing), I mentioned an idea of presenting language designs in this space as a puzzle to be solved, like a crossword puzzle. I invented the idea there and its been growing on me.

The previous week or so I'd been reading Sam Kamin's "Programming Languages: An Interpreter-Based Approach", so this didn't seem like such a crazy idea as it may sound. In "Programming Languages", Kamin starts with an interpreter for an extremely simple language using Lisp syntax, and procedes with each chapter to show what modifications need to be made to get interpreters for Lisp, Scheme, SASL, APL, Smalltalk, Prolog and others. They all use Lisp syntax, so the code changes are kept quite manageable, and the reader can focus on the essential differences in scoping, evaluation strategies, and the like.

It seems, as a first step, if the Language Design Crossword Puzzle were to be a reality, that making available a standard interpreter source such as Kamin's is a reasonable idea. "Given interpreter0, add macros" would be a puzzle. "Given interpreter0, add object serialization." This is similar in spirit to comments I made earlier about the utility of lambda calculus for studying language features.

But is the Language Design Crossword Puzzle a good idea? What's the point? Arcane Sentiment, a blog I discovered and subscribed to today, introspects on writing little language implementations. He describes certain parts of the exercise as "programming candy", and ironically, they're often the parts written in C, a series of little programming victories. The hard, ill-defined problems to be written in Lisp are the parts that tend to slow him down and demotivate him. (Arcane, I hope I'm fairly characterizing that post. Please correct me if not.)

I had to chuckle in self-recognition, as earlier this week I was watching the first few SICP videos, evaluating the examples in a Scheme-ish interpreter I'd whipped up on Monday and Tuesday, extending it during pauses in dialog while Sussman wrote on the blackboard. Until he hit the pi fraction example and I realized I wasn't at all sure if I wanted to right at that moment be writing code to rationalize denominators and factor fractions or whatever else Scheme might do to support exact rational number (fraction) arithmetic (e.g. (/ 1/2 (+ 1/8 1/3))). That problem at that moment was not interesting for me, and was not well-specified; are rationals always reduced to lowest terms? How is conversion to and from reals handled? I'd have to go study R5RS to learn the expected behavior. Handling the number tower was not my goal going into this project.

Why does Arcane Sentiment dabble in Lispy implementations? Why do I? Why reinvent the wheel? For me, it's a way to learn, to study. Toy implementations are rewarding, as they let you discard parts of a language implementation system that are indeed hard, and focus on particular points of interest. You need to be careful not to oversimplify, if you intend to take your lessons back to a real system. But this approach is something we advise junior programmers all the time: if you're struggling with how a library or language feature is working in the application, try writing a small example program first until you understand how it works.

So, I propose we have the best of both world. Language design problems can be programming candy, as well as programming spinach, that is something good for you. My wife has been making a spinach recipe from her Spain and Portugal cookbook which features raisins and pine nuts. It rocks.

The other question is, is there interest in a "language design puzzle" feature? Before we get to that, let me ask a more relevant question: what aspects of programming language implementation or operation are of interest to you? Macros? Evaluation strategy? Optimizations? Drop me a line to the Google mail account jfkbits and let me know.

Blog challenge: write a post using the phrase "free as in spinach".

Wednesday, April 30, 2008

StreamTokenizer and Declarative Lexing

One thing I've noticed about marketing is how frequently an appeal is made to change your lifestyle to include more of whatever is being sold. I first noticed this when I read in a catalog that Ikea wants me out of that rat race of the outside world, so I can spend more time at home. And by the way, don't I want my home to be a comfortable inviting place to spend time? After that, I've seen it everywhere. Here at JFKBits we want to know why the world doesn't write more language processors. Everyone can enjoy a world of recreational symbol translation. I was on vacation last week, reading a programming language book by the beach. Maybe someday we'll run programming language designs in this space and JFKBits readers can implement them as a kind of crossword puzzle of the day, in an hour on the train home from work. So today, we're thinking about how to get a lexer up and going more quickly.

When you're designing a syntax, it's typically done at a high-level:
  • Comment syntax: line-oriented or delimited, or both? do comments nest?

  • Identifier syntax: Limited choice for the first character (e.g. letters and '_'), followed by mix of alphanumeric and underscore. In Lisp, symbols syntax is much more flexible.

  • Operators and grouping syntax: parentheses, brackets, multi-character operators like ++, ->, and &&=.

It might be useful, in terms of quickly prototyping a domain-specific language or language-aware utility (e.g. a tool that finds buggy code patterns), to have a lexer generator that lets you declare properties in these terms rather than translating to regular expressions.

Java's StreamTokenizer, while not a universal tool, is a step in that direction.

What I like about StreamTokenizer is that it raises the level of programming closer to the problem domain. Regular expressions are the traditional and well-understood means of specifying a lexer's accepted language, but this declarative style is possibly a better programmer's tool. (Note well that I'm talking about StreamTokenizer, not StringTokenizer which is a much simpler state machine.)

For example, in playing with Kamin's interpreters with their S-expression-based syntax, I've been using this configuration to scan LISP-type code in Java:

tokenizer = new StreamTokenizer(new BufferedReader(reader));
tokenizer.resetSyntax(); // We don't like the default settings
tokenizer.whitespaceChars(0, ' ');
tokenizer.wordChars(' '+1,255);
The basic idea is that StreamTokenizer is a state machine with hard-coded states and transition arcs, and you configure it with what characters are in the relevant character classes. For example, from the state of skipping whitespace, there's a transition to a string literal state, when a character from the "quoteChar" class is encountered. The string literal state accumulates, transitioning back to itself on characters not in the quoteChar class. It's simply up to you to configure which character or characters constitute a quote delimiter. The essential observation is that lexers for many useful languages share state machines of identical shapes, and they differ only in the definitions of character classes.

Of course, not every language fits the preprogrammed state machine shape. StreamTokenizer can't even handle Java, because it has no capacity for multi-character operators. It can be configured so that '+' is an "ordinary character", meaning it is lexed as a single-character token, but there's no way for a parser to know if two '+' tokens in sequence came from the input "++" or "+ +". This is what I mean when I say StreamTokenizer is not a universal lexing tool.

But I still wonder if there's room for this declarative manner of input, building on higher-level concepts like identifiers and operators, for a more general lexing tool. This could be combined with a programmatic knowledge base of some of the standard lexical idioms running around. You could say "give me Python-style identifiers, with the standard Java operators except these four which don't apply to my language." I'm not at all sure there is need for such generality, but I think it's worth writing down, as an idea for future inspiration.

Thursday, April 17, 2008

Small Tokenizing World

I wanted to see what Java programs out there parse Lisp syntax using the handy StreamTokenizer, and the first one I found is Mike Bayne's, circa 1997.

Mike was one of the bright guys who did version 2 of the Prizm IDE that I helped work on for my senior project at Rose-Hulman. Now he runs his own online game company,, out of San Francisco.

Tuesday, April 15, 2008

AP Computer Science Language

I've been reading Sam Kamin's "Programming Languages: An Interpreter Based Approach" from 1990, which compares programming languages through the device of writing an interpreter in Pascal for a form of the language using Lisp-based syntax.

On reading all that Pascal source code, it takes me back. I reflect that I learned Pascal as a senior in high school, to prepare for the AP Computer Science test. That was in 1990. I see that the AP tests now use Java as their language. I wonder, was there any other language between Pascal in 1990 and Java in 2008?

If I had to bet on what language would succeed Java as that used for the AP exam, I'd bet on Python.

Friday, April 11, 2008

Variables as Objects in Ila

It's time for another in the series about Ila. This time we'll look at the var type and the Var[t] family of classes.

What is Ila? In January 1998 Uday Reddy presented Objects and Classes in Algol-Like Languages (refined in 2000). In Spring of 1998 I found myself Reddy's M.S. student, designing and implementing a call-by-value variant of the IA+ language presented there. I've taken to calling the implemented language Ila in this blog.

Second Class Objects

Let's look at another case of "everything is an object -- except when it's not." Pop quiz: how many objects do you see:

a = 1
If we take this to be from a language where "everything is an object", then there is at least one object: the integer 1. But what about a? Some would say it's just a name or reference to the object 1. But think about it this way. After this assignment, somewhere between the name a and the object 1 is a container. A container you can't "get your hands on": a container which can't be created on the fly anonymously or returned from functions; in short, a second-class citizen in the language, and furthermore not an object.

Notice I didn't say this language (which could be any one of "most" languages today) doesn't let you create containers. In fact, the simplest of all useful classes could be a simple container:

class Box
Object contents;
Object getContents() { return this.contents; }
Object setContents(Object src) { return this.contents=src; }

In order to be at all interesting, objects must have instance variables, some form of local state. Why not make variables be primitive classes?

References and Boxes

Before we look at what this even means and how this technique plays out in Ila, I did want to make a related work note. Explicit storage cell type is certainly out there, the ref types is part of what's biting Robot Monkey's shiny metal posterior, and there are others like box in Scheme. The difference with this approach is that var is an object. (I know, tortured sighs from certain parties. But for some people this represents the leveraging power of orthogonality. Ok. Groans from other corners. All right, let's move on.)

Var[t] - Variables as Objects

First, the formal introduction. In Reddy's IA+ paper, there was a var t polymorphic type and a family of classes Var[t] implementing it. The object signature for var t is {get : unit -> t, set : proc t}. So, given a variable object v we retrieve with v.get() and assign to it with v.set(k). That's the object syntax. As a built-in type it also can have special syntactic treatment to provide the more usual forms.

How do you declare a variable? Well, it's an object so you should be asking how you instantiate a new variable. More specifically, how you get a new Var[t] object. The Var[t] notation is generics syntax, you'd write Var[int] or Var[NuclearSubmarine] to talk about the classes for variables of specific types.) In Ila, the syntax for a new object has the form new id isa class-expr where id is the object name, in scope to the end of the basic block, and class-expr is a class-typed expression. More about class-typed expressions another time, here we'll just write the names of classes.

Putting it all together, here's a snippet of code using variables:

new usrname isa Var[str];
readstr("Hello, what's your name?",usrname);
println("Pleased to meet you, "+usrname+".");
println "Would you like to play a game?";
new score isa Var[int];
score := 0;
Aside from the new username isa Var[str] syntax, which is a little obnoxious and could be reduced to something like var username, the variable usage is entirely ordinary. Here we see

1. Implicit .get() call in the string expression "Pleased to meet you, "+usrname+".".

2. Implicit .set call in score := 0.

3. Passing the whole container so it can get updated in readstr("Hello, what's your name?",username).

To see how these work, we need to look at the types. In Ila, the type of an object is the type of its class signature, so usrname has the type {get : unit -> str, set : proc str}.

Let's look at these again in slow motion.

1. In username+".", we have something added to a string literal. In Ila, + is overloaded, so we only have a few choices, and from the string literal we resolve this to be the string + operator. So, the expression username is expected to be a string. But, it is not a string, it's a variable containing a string. What makes this work is a subtype relation in the type system and a coercion at runtime. The type var[t] is a subtype of t, and at runtime variables of t are coerced to be values of type t by calling the get method.

In other words, username+"." is implicitly turned into username.get()+".".

2. Assignments like score := 0 is simply syntactic sugar for score.set(0). The only other thing worth noting here is that there's nothing very vague or shadowy about what is an lvalue. The only things that can go on the left of the assignment are things with type var[t], or more correctly things for which var[t] is a subtype. If you wrote some arbitrary class and gave it a set method, you could put it on the left of an assignment operator.

3. Passing values of type var[t] to functions and procedures is similar to the first case, but you will want to know the type of the function or procedure's argument. If the type it expects is var[t], look out (as in the "bang" of Scheme's set!): it means the variable is being passed as a container object and its contents could be modified. In the case of the built-in procedure readstr this is expected.

Conclusion: Translation to Java

The Ila implementation needed to represent the Var[t] class in Java in a way consistent with the rest of the language. It was not possible to directly use Java local variables. As an optimization, yes, when their use matched the semantics of Java local variables. But as the general translation, I simply had to make a iap.lang.Var container class basically like the Box class mentioned earlier. This is probably where the idea breaks down, and I'm sure some readers have thought of this point already. Who wants to pay a method dispatch cost for every variable access?

If you tend to have a lot of getters and setters in your classes, or if you're attaching listener management methods for lots of an object's state, consider that a variable object could be one place to hang all that functionality, as methods of the variable itself instead of methods of its containing class. Try obj.field.addListener and obj.field.set on for size instead of obj.addFieldListener and obj.setField. To the degree that "everything is an object", that universal orthogonality, is useful, to the degree that it is useful for metaprogramming, this technique deserves some consideration.

Wednesday, April 02, 2008

Next Time Think of Some Tests

If you volunteer to help your sister-in-law with wedding preparations on Thursday, and you don't get to it until Friday, and you decide to write a program to do it, don't forget to think about some basic sanity checks on the final output. Otherwise on Sunday you'll hear from your father-in-law wondering why some people didn't have placecards and didn't know where to sit.

So yeah, wedding preparations in the sense of "can you research how to go from an Excel spreadsheet of names and table assignments to a Word document with the names in the right places to print on these pre-scored placecard sheets from Hobby Lobby, SKU #717694."

The more you think about Excel, you think "Not too bad, Mathematica imports from Excel," and the more you think about Word you think "Ugh". And the more you think about Mathematica, the more you remember the vector graphics language, and that you can trivially export to PDF or rasterized image files.

tables = Import["c:/tables.xls"];
sheet = First[tables];
(* Extract name from row by pattern match *)
nameOfRow[{title_, names_, ___}] :=
trim[title] <> " " <> trim[names];
(* extract table assignment text from row *)
tableOfRow[{_, _, _, tbl_, ___}] := trim[tbl];
(* filter out blank rows *)
rowsWithNames[sheet_] := Select[sheet,
Function[row, trim[row] =!= ""]];
Some Opening Lines of Code, Which May Become Important Later

Not very long after, it seems, the Excel spreadsheet is imported, blank rows are skipped, the names and table numbers are constructed and placed onto the vectorized layout of the placecard sheet, with or without preview construction lines. Very cool.

placecardPageTemplate[] :=
With[{w = placecardPageWidth, h = placecardPageHeight,
pgborder = placecardPageBorder},
(* Solid page border *)
Dashing[{}], Line[{{0, 0}, {w, 0}, {w, h}, {0, h}, {0, 0}}],

(* Scored page borders *) Dashed,
Line[{{pgborder, 0}, {pgborder, h}}],
Line[{{w - pgborder, 0}, {w - pgborder, h}}],
Line[{{0, pgborder}, {w, pgborder}}],
Line[{{0, h - pgborder}, {w, h - pgborder}}],

(* Scored between-card borders *)
(* vertical *) Line[{{w/2, 0}, {w/2, h}}]}
Table[With[{cardHt = pgborder + i*placecardHeight},
Line[{{pgborder, cardHt}, {w - pgborder, cardHt}}]], {i, 1, 2}]
Flatten[Table[placecardTemplate[r, c],
{c, 1, numPlaceCardColumns},
{r, 1, numPlaceCardRows}], 2]];
Sample of the Vector Graphics Code

More time is spent rasterizing, with long interruptions for meals, toddler nap and bedtime, and the necessary socializing that comes from being in the bride's family's house the day before the wedding (e.g. rehearsal and dinner).

By late evening the table assignments are finalized and the requested high-resolution JPGs are being rasterized from the vector graphic objects. Sometime the next morning, the placecards are printed. The ceremony comes off with only one hitch, and by evening the reception is ready to swing.

Except... for that one little hack. When you wrote that simple filter to remove blank rows, you did it by checking if the first column was blank. And as it turns out, the first column is for titles and some names, about 6, didn't have a title.

Fault? Everyone agreed it was the you the programmer's. Some issue can be made about the the given spreadsheet format, with a separate column for titles. But the bottom line is you had all the data, and simply spent too much time coding and not enough time planning. There was time to do it right, and no time to do it over. There should have been some time devoted up front to thinking about how to check for correctness of the final output.

Oh well. The next time someone asks to help print placecards you're all set...

If you are interested in the Mathematica notebook that can generate custom placecards with your database of names, send to the account jfkbits. And please note I've fixed the aforementioned bug.

Tuesday, April 01, 2008

April Curmudgeon

Disclaimer: The April[0] Post you are about to read is not meant to be amusing. Please adjust your expectations now. Lighthearted, yes, but it will not make you laugh aloud. Really, it will not be amusing unless you somehow make it so by assigning a meaning it was never intended to have. By reading this post hopefully you will gain insights that allow you to be a funnier blogger. When Frank Bunker Gilbreth's children, whom he was teaching to touch type, asked if he could touch type, he only replied "They tell me Caruso's voice teacher can't sing a by-jingoed note." May it be so with this post.

It's challenging to write truly good April Fool's material about programming issues, but almost programmatically easy to write lame material. One reason things are funny is that (1) they violate expectations, and that (2) they do so in a way that doesn't personally impact you, as in Mel Brook's observation "Tragedy is when I cut my finger. Comedy is when you walk into an open sewer and die".

We're immersed in dark humor by the nature of our process-based profession. Programmers with customers (the most interesting kind of programmers) keep huge databases of failed expectations. These only get funny with distance: either in time or in organizational chart hops. Your coworkers' bugs are more likely to be funnier than your own, but only until your manager decides to reassign to you. Another team's bugs are funnier. Unless you rely on that feature. And so on.

The other kind of expectation, that program P (browser, language, Turing-capable text editor) expects input format X and generates output format Y, are also targets for humor: "Bwahaha, a web browser that accepts COBOL as an HTML scripting language" if it's well-known that this combination doesn't exist and doesn't seem to make sense. Humor playing on this type of expectation is fragile, because the expectations are broken on purpose all the time by the current of software development progress. It's only a matter of time when "Ruby VM in Javascript" moves from being funny to being accepted way of life. Maybe COBOL is funny today, but legacy systems have a way of creating needs that can be solved by software. If you want a joke candidate generator, write a program that generates T diagrams with all possible combinations of known programming languages at the different points. The funny ones will be funny because they violate the intended design of the language: Logo as an implementation language for a Fortress to Haskell compiler. (It's probably a good sign for a language if it's never funny at any point on the T.)

Take a look at the April Fools gags out there related to programming and see how many are analogous to "that idiot tried to plug a USB cable into a Firewire socket". The DailyWTF material is kind of a catalog of such expectations:
  • You should write code without explicitly specifying every input case

  • Code should have a purpose, unlike this if check:
    if( nextIndex != currIndex )
    nextIndex = currIndex;

  • You should use a standard library function rather than writing your own buggy version

  • You shouldn't transform data through several unnecessary layers (the digital camera/wooden table technique)

  • Code should, ideally, do something productive, especially if you're paid to create it
The real humor, the best humor in programming topics and others, is the kind that also incorporates the self-recognition element, which I think is simple imitation or mimicry in its rawest form. This is the Jerry Seinfeld style, where you observe and describe a situation or behavior. There's something about hearing a description of a behavior, especially one we wouldn't readily admit to unprompted, that makes us laugh when we recognize we're guilty of it too.

Note: COBOL is one of those all-purpose humor words, kind of the "weasel" of programming humor. Source: Ask Mr. Language Person.

Lame subtlety spoiler: If you skipped the disclaimer, and thought this was supposed to be somehow funny just because it's April[0], check the title. Also, it's not realistic to expect to get a funny blog post in polynomial time from the T-diagram generator. Not that I tried.

Wednesday, March 26, 2008

Planes Without Heaps

I ran across something interesting while reading up on abstract interpretation. I was prompted by a redditor comment that the approach in "Symbolic Disassembly" was an abstract interpretation technique. Patrick Cousot's team has a static analyzer for C code that they've applied to software in the Airbus A340 and A380:

The development of ASTRÉE started from scratch in Nov. 2001. Two years later, the main applications have been the static analysis of synchronous, time-triggered, real-time, safety critical, embedded software written or automatically generated in the C programming language. ASTRÉE has achieved the following two unprecedented results:
  • A340-300 In Nov. 2003, ASTRÉE was able to prove completely automatically the absence of any RTE in the primary flight control software of the Airbus A340 fly-by-wire system, a program of 132,000 lines of C analyzed in 1h20 on a 2.8 GHz 32-bit PC using 300 Mb of memory (and 50mn on a 64-bit AMD Athlon™ 64 using 580 Mb of memory).

  • A380 From Jan. 2004 on, ASTRÉE was extended to analyze the electric flight control codes then in development and test for the A380 series. The operational application by Airbus France at the end of 2004 was just in time before the A380 maiden flight on Wednesday, 27 April, 2005.

The analyzer has its limits, so by extension does the tested code: "ASTRÉE analyzes structured C programs, with complex memory usages, but without dynamic memory allocation and recursion." Of course we don't know from this whether there is other code run in the Airbus 340 or 380 that does use dynamic memory allocation, but presumably the 132,000 lines of C are an important and interesting part of the system. So, it's a largish useful program that doesn't use the heap.

Do you remember the last time you wrote a program with no dynamic memory allocation (in a language that doesn't do it as a matter of course)?

Wednesday, March 19, 2008

Symbolic Disassembly

In looking at OCaml-generated x86 assembly last week, I noticed that having a language which keeps undefined identifiers in symbolic form can be handy. I started making notes in a Mathematica notebook to keep track of some heap shuffling code I was trying to understand. To explain the technique, let's use this OCaml snippet:

((1.0 -. alpha) *. (Array.get y i))
where the floating-point arithmetic becomes this x86 code:

fsub REAL8 PTR [eax]
fmul REAL8 PTR [esi]
In Mathematica, I translated lines of assembly into real assignments, using the literal register names for my variable names, except at the very beginning of the assembly fragement. For example, when starting the above fragment, eax points to the alpha value, so I would write the read reference to eax as alpha, without defining alpha. Similarly esi points to Array.get y i, so I was able to write this sequence:

It was interesting, a little startling actually, to see the original expression re-emerge by simulating running the code. I didn't get very far into it, but you can also do things like simulate writes to memory with a register transfer definition:

Mem[eax] = 2301
In a traditional language, eax has to be bound to a value. But in a symbolic language, eax can be a symbolic expression like _caml_young_ptr + 4.

Do my partial-evaluation readers have any remarks about this?

Friday, March 14, 2008

List Append and List Representation

When writing "RC Filter with OCaml" I was surprised that list append performed so poorly (is not tail-recursive). As explained earlier, the RC algorithm is defined as processing elements from the input array from first to last, but in doing so new elements in the result list must be appended, not prepended (cons). Since OCaml didn't have a constant-time way to append to a list, I was forced to prepend and reverse the result later.

It depends on the list data structure I think. If lists are represented with a simple cons cell, namely a pair of head and tail pointers, then there's no other way to do it. But lists could be represented with a list header containing information such as length and last element pointer to speed up certain operations, as well as the pointer to a chain of traditional cons cells:

struct ConsCell {
struct ConsCell* hd;
struct ConsCell* tl;
typedef struct ConsCell* LinkedList;
struct ListHeader {
unsigned length;
ConsCell* first;
ConsCell* last;
typedef struct ListHeader* List;
Representing lists with the header makes several operations constant-time: appending or prepending an element, concatenating two lists (called append in ML), and getting the list length. It does so at an obvious memory overhead cost, as well as the time cost of an extra level of memory indirection: getting the head or tail has to read header->first as well. As I found in the generated assembly, OCaml calls a hd function anyway, so as for it I don't think that's a concern. And I imagine the Ideal Functional Language Optimizing Compiler (IFLOC) would identify places in the source where the simpler LinkedList would work and just use that.

Wednesday, March 12, 2008

RC Filter with OCaml

In "Dependent Iteration" we looked at a small numeric program given in imperative programming style and wondered how it might look in functional or hybrid environments, and whether it would perform well. I felt the RC filter algorithm posed some challenges for being elegantly expressed in a functional style, in a way that might be appealing to procedural programmers but that also is fast. In "RC Filter with Python and Java" we got some real numbers for an input file of about 1.2 million entries. What I really wanted to try was a compiled functional language, like OCaml. So, now we can add OCaml, procedural and functional variants, to our previous results (note Psyco-enhanced Python was added, see post comments):

Language Total Time/Iteration
Java 29 ms 24 ns/iteration
OCaml native procedural 56 ms 47 ns/iteration
OCaml bytecode procedural 547 ms 456 ns/iteration
OCaml native functional 940 ms 783 ns/iteration
Python with Psyco 588 ms 490 ns/iteration
Python 1507 ms 1255 ns/iteration
OCaml bytecode functional 1692 ms 1410 ns/iteration

I was surprised to see OCaml not beat Java. I am using the OCaml compiled for the Microsoft toolchain, for which there is a release note about degraded performance from lack of computed gotos; maybe that's it. It was interesting to see the bytecode times so similar to the Psyco-enhanced Python version. The functional version is just a bit disappointing, partly because I had to reverse the list.

Let's take a look at the code, and some of the practical things I learned about getting started with OCaml.

Fractal Benchmark Page

My favorite resource for this post is this Fractal Benchmark page, from which I gleaned two clues about OCaml:

1. Fine-grain timing (under a second) can be done with Unix.gettimeofday().

2. OCaml has for loops:
for i = 1 to 10 do
print_int i

Using OCaml Modules

If you bother to read the documentation ahead of time, you won't get caught here. But silly me, given the preceding benchmark code and the fact that the Unix module is in the OCaml library documentation, I assumed Unix.gettimeofday() would work out of the box.

No, if you want to use the Unix module, and you're running the ocaml interpreter, you need to first use the #load (that's "pound load", one word, not the "#" prompt followed by a load command) directive:

#load "unix.cma";;

You have to know to use the lower-case name "unix" to load a module with the capitalized name "Unix", and you have to know the special file extension ".cma". Did I mention that you need to do this with some modules, but not others which come pre-loaded, and I'm not sure I can tell you which ones are like this.

I didn't really find this the most user-friendly introduction to getting something done, you can draw your own conclusions, but the cherry on top was the next point.

If you want to compile source code, you must not have a #load directive in the source code. Presumably one can load source code into the interpreter, as you can with SML/NJ's use command, and if so, does that mean you need to manually type the #load(s) first? This seems incomprehensible. Obviously not a showstopper issue to the OCaml community, one way or other.

What you do need to do if compiling with a module like Unix is to mention its compiled module file to the compiler. I needed to list the module before my source file. Here's my bytecode compile command:

ocamlc -o lp.exe unix.cma

Using the Native Compiler

I had installed OCaml for the Microsoft toolchain. I needed to do just a couple setup things:

1. Make sure the Visual C bin directory is on the path:
set PATH=C:\Program Files\Microsoft Visual Studio 8\VC\bin;%PATH

2. Make sure the LIB environment variable has a path of the Microsoft library directories:
set LIB=C:\Program Files\Microsoft Visual Studio 8\VC\lib;C:\Program Files\Microsoft Visual Studio 8\VC\PlatformSDK\Lib
If you don't have #1 right, you get a poignantly confusing error message:

'ml' is not recognized as an internal or external command,
operable program or batch file.
Assembler error, input left in file C:\DOCUME~1\jfkbits\LOCALS~1\Temp\camlasm705c28.asm
The "ml" mentioned here is the Microsoft Assembler, not any ML language thing.

The compile command for the native compiler is like that for the bytecode compiler, only you change .cma files to .cmxa:

ocamlopt -o lpopt.exe unix.cmxa

Procedural Code

Without further ado, the procedural code:

let lowpassProcedural x dt rc =
let n = Array.length x in
let y = Array.make n 0.0 in
let alpha = dt /. (rc +. dt) in
Array.set y 0 (Array.get x 0);
for i = 1 to n-1 do
Array.set y i (alpha *. (Array.get x i) +. ((1.0 -. alpha) *. (Array.get y (i-1))));
This is about as close as it gets to the universal procedural implementation: arrays and for/do loops. Notice that overloading is not to be found in OCaml, so the floating-point operators have identifiers like +. and *..

Functional Code with Fold

The correct code:

let lowpassFunctionalFold x dt rc =
let x0 = List.hd x in
let alpha = dt /. (rc +. dt) in
let helper acc xi =
match acc with (yprev,ys) ->
let yi = alpha *. xi +. ((1.0 -. alpha) *. yprev) in
(* (yi,ys @ [yi]) don't do this *)
(yi, yi::ys)
match List.fold_left helper (x0,[]) x with
(_,acc) -> List.rev acc (* rev accounts for about 40% of the running time *)
Turn your attention to the last line of helper where the returned list is constructed. The given implementation uses :: (cons) and the result is reversed at the end. The reverse is done to give the proper ordering of the output list when the list elements are visited first to last as with fold_left. Note that we must visit first to last, because the RC filter algorithm is specified that way. (Even if it works to filter a signal with time reversed, I'm looking for code that can be explained to those familiar with the subject.) This means we can't use fold_right.

As noted in the source, I originally wrote this using @ (list append) to tack elements onto the end of the list. But this is exactly what the documentation is warning about when it says "Not tail-recursive." I gave up timing that implementation. OCaml could use snoc here (append to the end of a list, counter to cons which prepends).

There may be a better way to do this in OCaml using fold or similar list iterator. I was simply trying to get a reasonably compact functional definition that didn't degenerate into hand-coded recursion.

Updated: Added native compilation numbers and commentary.

Friday, March 07, 2008

RC Filter with Python and Java

Following on to "Dependent Iteration", I tried the RC filter simulation on a semi-realistic problem with 1.2 million iterations in a few platforms. The two I want to report on seem to run the gamut of fast to slow:

Language Total Time/Iteration
Java 29 ms 24 ns/iteration
Python 1507 ms 1255 ns/iteration

I ran the filter function in a loop and averaged the times to report the numbers above. The Java code is reasonably close to the metal here: on a 3GHz CPU at 0.3ns/cycle, 24ns is 72 CPU cycles to perform 3 double precision arithmetic operations and two array lookups and some loop overhead, probably with cache block fetches amortized across the life of the loop:

public double[] lowpass(double[] x, double dt, double RC) {
double[] y = new double[x.length];
double alpha = dt / (RC + dt);
y[0] = x[0];
for(int i=1; i<x.length; ++i)
y[i] = alpha * x[i] + (1-alpha) * y[i-1];
return y;
There must be a better way to do this than my Python code (running on version 2.5.1). Aside from whether this uses single or double-precision arithmetic, I tried using both arrays and lists, and reported the faster (the list version, actually):

def lowpassArray(x,dt,RC):
alpha=dt / (RC + dt)
for xi in x[1:]:
y[i] = alpha * xi + (1-alpha) * yprev
return y

def lowpassList(x,dt,RC):
alpha=dt / (RC + dt)
y = []
for xi in x[1:]:
yi=alpha * xi + (1-alpha)*yprev
return y
One interesting thing in these exercises is that for the number of language platforms I'd like to try, it takes a nontrivial amount of time to figure out (a) how to load from a file in one-float-per-line format and (b) how to get wall-clock time within the environment.

What about your favorite functional or scripting platform? How fast can you get this dependent iteration loop with an input size of 1.2 million?

Wednesday, March 05, 2008

Dependent Iteration

Consider the following code:

// Return RC low-pass filter output samples, given input samples,
// time interval dt, and time constant RC
function lowpass(real[0..n] x, real dt, real RC)
var real[0..n] y
var real alpha := dt / (RC + dt)
y[0] := x[0]
for i from 1 to n
y[i] := alpha * x[i] + (1-alpha) * y[i-1]

return y
This is from the section "Digital Simulation" from the Wikipedia article "Low-pass filters" and it has an element that strikes me as fundamental in the "for loops considered so 20th century" mindset. Each iteration uses the results of the previous iteration.

The example code is a digital simulation of a physical phenomenon, a simple resistor-capacitor (RC) circuit which allows frequencies below the cutoff and blocks frequencies above the cutoff. The y[i-1] is helping model the physical phenomenon of the first derivative of output voltage which the capacitor introduces.

Similar physical reasons, like neighboring physical objects and derivatives, make it very natural to use the procedural paradigm where access to neighboring data and previous calculation results involve array access. The whole area of physical simulation programming, including digital signal processing, is centered around the procedural programming paradigm, and pseudocode and examples are largely in terms of x[i], y[i-1] notation. And when they write for or do loops, they might often be for a million, ten million, or more elements. Speed in everything matters on those kinds of input orders of magnitude.

In light of these requirements, can this type of programming be done in a functional style? Should it?

I helped a customer fix a performance problem in some code very similar to this in the "current iteration depends on previous iteration's results" sense. Access to his output data structure was slowing things down and we solved the problem by using a local variable to remember the previous iteration's output value. But I started wondering what a good general iterating idiom would be for this type of problem: one that lets the dependent iteration be expressed elegantly, but one that also performs well.

A directly recursive version might look like this:

fun lowpass(x,dt,RC) =
val n = length x
val alpha = dt/(RC+dt)
fun lowpass' i yprev acc =
if i >= n then
let val yi = alpha*sub(x,i)+(1-alpha)*yprev
lowpass' (i+1) yi (append(acc,yi)
lowpass' 0 (sub(x,0)) []
With a good native compiler this should perform well, the tail recursion optimized to an assembly jump and the lowpass' function parameters assigned to registers. But is this as intuitive? It certainly looks longer than the procedural version.

Of course this is also a natural for fold, with the previous output value included in the accumulator spot. But I wonder if it's less intuitive than the explicitly recursive version, and I wonder if the performance can possibly come close to the metal lanugages unless the compiler can inline fold's function argument and reconstruct the implicit loop.

I think a list-comprehension version would be more compact, and provide both readability and performance. The Mathematica version using Table is reasonable:

lowPass[x_, dt_?NumberQ, RC_] :=
Module[{yprev = First@x, alpha = dt/(RC + dt)},
With[{ycurrent = alpha*x[[i]] + (1 - alpha)*yprev},
yprev = ycurrent;
{i, 1, Length[x]}
But then this is not purely functional: it uses a stateful local variable yprev. The fold option may be the best purely functional one, but it still seems like a hybrid has the best chance for high performance while not needing the for/do loop token overhead.

Monday, March 03, 2008

Quickie: Sometimes Simpler Is Harder

The Microsoft Knowledge Base article "How to Automate Folder Permissions" recommends creating three files: Addperm.cmd, Addperm2.cmd and Yes.txt.

As you know or can guess if you've used the cacls command, Yes.txt contains just the letter "y" and is piped or redirected to cacls:

cacls %1\%2 /T /G Administrators:F MUG2000\%2:C "MUG2000\Domain Admins":F <\yes.txt
What gave me a chuckle was the line "The third file is a little more difficult" in the directions, which I've abbreviated here:


(17 lines of script code here)


(6 lines of script code here)

The third file is a little more difficult.

Open a command prompt (Cmd.exe) and change directories to the root directory of the drive to which you have saved the other two files.

Type the following:

This creates a text file with the Y and ENTER needed to automate the CACLS command.

It's funny, but I can't argue with them too much. What's the alternative? A gray box with the single letter "y" in it?

Friday, February 29, 2008

Types and the Meaning of DFT

Sometimes it's good to get outside your comfort zone. These past few weeks have been like that for me, leaving behind the comfortable world of lambda calculus, type-directed translation, web frameworks, and instead trying my hand at some digital signal processing (DSP). In this post we're going to wrap up the discussion of types, meaning, contract and documentation using the topic of the Discrete Fourier Transform (DFT).

DSP: A Different World

This all started with some customer visits I made earlier this month, customers at large corporations doing lots of DSP, with more of a fondness for producing field-programmable gate arrays than writing news aggregators in 600 lines or less. It's refreshing to peek under the lid of other technical fields and see their complexity, to read things like "this project required tight coordination between the FGPA designers and DSP programmers who typically do not share design tools." It's the realization that it's a big technical world out there - that there are whole categories of developers with different skillsets and toolchains, where in a sense C is not close enough to the metal. Remember the advice that you always need to ask "for what" when hearing a recommendation for a new language or framework? Yeah. It matters what you're doing.

One outgrowth of those visits was an initiative on my part to write some basic signal processing programs. For example, I wanted to simulate the Amplitude Modulation process: modulate a .wav file sound clip onto the carrier frequency from the standard US commercial AM radio band (600KHz to 1600KHz), look at the frequency domain graph to see the expected carrier frequency spike and sidebands (corresponding to the original sound clip), and then demodulate it and play back the resulting sound file. Apparently this style of simulating the over-the-air bitstream is commonplace for those in the business of making things that go over the air (or through optic fibers).

I Heard This is Supposed to Hertz

The essence of the DFT is not hard to grasp, once you understand the basic premise of Fourier analysis: that any given time-based function (a.k.a signal) can be equivalently represented as a sum of periodic functions, sines, of various frequencies and magnitudes. In very simple terms, if you hit four tuning forks of different music pitches, the resulting sound could be represented as either a complex-looking wavy line or the sum of four sine waves of different frequencies (and phases). The DFT simply works with discrete samples of the input signal or function and is more suited to processing with a digital computer.

What I discovered and reported in Look at the Types... If You're Lucky is that the writings about the Discrete Fourier Transform (DFT) are surprisingly slippery on the topic of physical interpretation. What I wanted most from the DFT was a frequency spectrum plot with Hertz (SI unit Hz, defined as cycles per second) on the bottom axis and power on the vertical axis. I could tell what programming language type the DFT functions took and returned (arrays of complex numbers). Given the array of complex numbers it is easily converted to an array of magnitudes which you can then plot. But the units of the plot? That was another matter.

Both in general discussions of the DFT and in library function documentation, I got lots of (a) definitions of the DFT array and (b) useful tips like "you can plot the magnitude to see the spectrum " and "the first element in the returned vector is the DC component".

But over and over I could not get a straight answer to the question "what are the actual frequencies" and "what units are the magnitudes"; essentially what are the units when plotting the magnitude of the DFT complex numbers.

Typical DFT Documentation

Here's a typical example of DFT documentation, the Apache Math library's FastFourierTransformer class:

public Complex[] transform(double[] f)
Transform the given real data set.

The formula is $ y_n = \Sigma_{k=0}^{N-1} e^{-2 \pi i nk/N} x_k $

f - the real data array to be transformed

the complex transformed array

Notice the DFT definition is given, though typically the free variables y_n, N, and x_n are not defined. The reader is assumed to be familiar with the definition.

How to Get the Hertz, the Power

Eventually I stumbled on Julius O. Smith III's excellent summary of the DFT. I say "excellent" because it spells out in satisfying detail what the notation means and what the units are.

Briefly, if the DFT function returns an zero-based array X, then X[k] represents the frequency k/Ttotal where Ttotal is the time duration of your input sample. That's it!

So, Smith gives us the Hertz. For the vertical axis, I had to consult a friend with a PhD in communication theory to get the explanation for the magnitude. Of course the meaning of the magnitude depends on the meaning of your input signal. After all, the time domain samples could have a range of 1 Volt or 1millivolt, the input array doesn't have units either. Briefly, whatever units of power the input squared has, the DFT magnitude squared also has.

Types, Contracts and the Real World

Every programmer learns how to model the real world with types as well as code. We realize there's not a one to one match between data and reality, and finding the right tradeoff is important to success. Some kinds of bugs can trace their origin to a data model that is too simple: there are real world states that can't be represented. Other bugs arise when the data representation has states that correspond to no real world state. Other bugs arise when the data model is so complex that the programmers can't keep up with it. I claim that the best software solutions are written by experts in the problem domain, and have a data model that models the problem domain as exactly as possible. The problem domain experts have no problem keeping up with the data model because it matches their understanding of the real-world processes that they carry with them when they're away from the source code.

The Discrete Fourier Transform is best described as a library function, because it has applications in so many fields and areas. The best software solutions using the DFT are undoubtedly written by people who have studied the topic away from a source code editor. Sitting in front of a Javadoc is no place to learn DSP. It's also no place to learn about Swing, or X.509 certificates. But I do think a modicum of domain explanation is appropriate in documentation for these types of libraries, for newcomers who know what they need out of the library without needing to know implementation details. It's a tricky line, but after being in this situation, I'm more sympathetic to this position of a library consumer.

In summary, I'd like to propose that library documentation generally have three kinds of information:

1. The function prototype, describing the types of parameters and the return value.

2. Low-level invariants and contract information about the arguments and return value.

3. A little bit about how the function relates to the real world.

Improved Documentation

Finally, here's my documentation attempt for the DFT function:

Complex[] dft(double[] signal);
returns the Discrete Fourier Transform of the input array signal.

If the input signal is an array of N signal samples taken at sampling period T, implying that the input signal has time duration NT seconds, then the returned Complex array also has N frequency components. The kth element of the array corresponds to the frequency k/(NT) cycles/second. If the squared value of the elements of signal is in power units P, then then squared value of the elements of the returned array also have power units P.

The elements in the first half of the returned array are mirrored by the elements in the second half, as they correspond to the positive and negative frequencies respectively.

signal - Input signal, a length N array of signal samples taken at sampling period T.

Array of length N of complex numbers. The kth element of the array corresponds to the time-domain frequency k/(NT) cycles/second. The magnitude squared of a complex-valued element in the array corresponds to the power for that frequency, and the angle of the complex-valued element corresponds to its phase.

IANADSPG (I Am Not A Digital Signal Processing Guy), so don't bet your company on this description, and do please send me corrections (citing sources). This is simply the type of thing I'd have liked to know when first coming to the DFT, and I hope by analogy you can find insights how users of your library will view it and how you may want to document it.