Author Archive

Last week, my colleague Ken Overton and I attended the IFL 2009 conference in South Orange, New Jersey.  The event was partially funded by Jane St Capital, and consisted of research on the implementation and application of “functional languages.”  The invited talk was by Benjamin Pierce (of TaPL fame), on his joint work (with Nate Foster and others) on the bidirectional programming language Boomerang.  The conference’s full range of subjects was diverse, and in this article I will summarize what I saw.  Read more...

Any British citizens reading this weblog might consider signing this petition, which is already gathering a lot of press from the BBC and CNN.

In the last article, we explored the concept of data-types as algebraic expressions, and the idea that the derivative of these expressions produces their type of one-hole contexts.  This “leap of logic” gives us a firm foundation for purely-functional incremental mutation, and (more generally) proof that there are interesting things happening at the level of types!

Still, many good ideas are destroyed (or exalted) when the time comes to make a real program out of them.  So in this article, we will write that program, and in the process shore up this notion of a derivative by defining it over any recursive type.  Read more...

With the spreading popularity of languages like F# and Haskell, many people are encountering the concept of an algebraic data type for the first time.  When that term is produced without explanation, it almost invariably becomes a source of confusion.  In what sense are data types algebraic?  Is there a one-to-one correspondence between the structures of high-school algebra and the data types of Haskell?  Could I create a polynomial data type?  Do I have to remember the quadratic formula?  Are the term-transformations of (say) differential calculus meaningful in the context of algebraic data types?  Isn’t this all just a bunch of general abstract nonsense?

We’ll investigate these questions, and perhaps demystify this important concept of functional languages.  Read more...

In writing functional programs, we’ve learned to put aside many problematic techniques for writing programs, especially iteration and mutation over data structures.  On the other hand, some folks aren’t buying in to this functional nonsense, and they continue to build elaborate (and working, they will remind you) software based fundamentally on algorithms incrementally mutating data structures.

Can’t we all just get along?

(An answer inside, plus the continuation of our exploration of type-classes.)  Read more...

We’ve already seen that type-classes enable a very rich form of ad-hoc overloading (especially for basic arithmetic, where other languages require awkward workarounds).  If that were all that we could do with type-classes, it would more than justify their existence in a language.  However, that’s not all that we can do with type-classes — they’re good for much more.  Read more...

Last time we compared arithmetic overloading and type-inference in F# and Haskell.  We even created our own numeric type in Haskell, as represented by Peano numbers, by implementing a type-class instance.  This stood in contrast to F#’s fixed set of numeric types (whose overloading of arithmetic functions was treated as a special case by F#’s type-checker).

APL/KDB programmers don’t have the benefit of a type-checker, but they do have some sophisticated overloading of arithmetic types.  Here we’ll see how we can recover APL-style arithmetic in Haskell, properly typed, and discover an important generalization that should further the argument that type-classes would be a valuable addition to F#.  Read more...

By now, you’ve probably heard the standard line.  Functional programming is all sweetness and light; if we merely cast off the detritus of bad habits we’ve learned from C, C++ and Java we’ll find ourselves in a different world, a better world.  Without state, and by dint of a civilized logical system of analysis, all wishes will come true.

Yet, in the world of F# (and OCaml in a slightly different case), we encounter some logical anomalies:

> (+);;
val it : (int -> int -> int)
> 3.2 + 5.4;;
val it : float = 8.6

Which is the truth here?  Initially we’re told that the “+” operator expects two int values, but it seems to happily accept two floats.  Worse yet, if we expect to rely on this magical addition, our hopes are soon dashed:

> let twice x = x + x;;
> twice 9.4;;
  ——^^^
stdin(2,5): error FS0001: This expression has type
    float
but is here used with type
    int.

Our only chance for generic arithmetic (over ints, floats, vectors, etc) is to explicitly pass the necessary arithmetic functions around:

> let twice fn x = fn x x;;
val twice : (’a -> ‘a -> ‘b) -> ‘a -> ‘b
> twice (+) 1;;
val it : int = 2
> twice (+) 1.2;;
val it : float = 2.4
> twice (fun (a,b) (c,d) -> (a+c,b+d)) (1,2.3);;
val it : int * float = (2, 4.6)

And although this works, it has a kind of Jerry Seinfeld “why don’t you just tell me the function you want to call?” feel to it.  There must be a better way.  Read more...

Maybe you just have large fingers.  Maybe you serve some traders, through a trade-entry language, and they have large fingers.  Whatever the reason, humans misspell words.

If you write software for humans, or if you yourself are a human, read on for a simple, classical solution to this ancient problem, expressed concisely in F#.  Read more...

At this point we’ve developed a complete, though very simple, interpreter and runtime environment.  To some degree, this interpreter is all we need.  It can express any function, it can easily be extended, it has a simple parser, and it has a working garbage collector.  What more could we ask for?  Life is good.

Life is good, that is, until we ask somebody else to use it.  Their first response is probably an annoyance at the syntax — it’s a little surprising to have to write (+ 1 1) after grade school has burned 1 + 1 into our minds — and, truth be told, the S-Expression syntax isn’t the most natural or compact for every problem.

Luckily we can, with a little work, entirely eliminate this complaint by creating a parser generator — a function that takes as input a grammar (a formal description of a language), and produces as output a parser for that language.  Read more...

In the previous articles of this series we’ve seen how to create a simple Scheme interpreter, then how to write an S-Expression parser to feed the interpreter, and in the last article we saw how to most conveniently bind C++ functions to our interpreter with the strategic application of template classes and a “meta-circular” code-generator that built up a vital part of our interpreter (using our interpreter to do it).

Though we’ve come a long way, there’s still one glaring hole in our interpreter design: we’ve left the allocate<T> function unspecified.  This function is meant to allocate a garbage collected value of type T, which implies that we’ve got to write a garbage collector.  In this article, that’s exactly what we’ll do.  Read more...

In the first article we saw how to build a simple interpreter.  In the second we saw how to create a parser for S-Expressions, which could be used to prepare the input to our interpreter.  So far we have a well-organized interpreter with a simple syntax (for which we’ve created a simple parser), but there are still a couple of barriers to using this interpreter in a real project.  First, it’s very awkward to bind existing functions to the interpreter — ideally we’d just like to point the interpreter at functions we wrote last year (or library functions like sin) without having to write a lot of boilerplate.  Second, we’ve developed a pretty sparse offering of functions, and we ought to fill that out a bit more if we hope to do anything useful with our interpreter.

In this article we’ll address those issues, and we’ll find that this exercise results in our tying a Gordian Knot, wrapping everything we’ve done into a nice little package.  Read more...

In the last article we saw how to build a simple interpreter.  We quickly ran into the problem that complex program terms (like the definition of the factorial function) were incredibly difficult to construct manually.  In this article we’ll address that problem by first establishing a shorthand for program terms: S-Expressions.  Then we’ll see how we can mechanically translate textual S-Expressions into the linked Pair structure that our interpreter requires.  Read more...

“What?! You’re going to create another programming language? It’s going to be too hard for new people to learn, and there’s just too much complication involved! Interpreters, type-checkers, compilers, parsers, garbage collectors: these things are too difficult for average programmers to understand. And what’s the real business value anyway? You shouldn’t reinvent the wheel! Have you taken a look at Jimmy’s XML configuration system? He says that his files let you just wire up components, and surely that’s simpler than a new language.”

This series of articles on practical programming language theory (PLT) will be an answer to the above refrain. In this first article, I’ll show just how simple it is to make an interpreter for a basic functional language using any modern C++ compiler.  Read more...

I’ve made some updates to this project since I last wrote about it.

I added basic perspective-correct texture mapping (the image to the left shows the Lab49 logo mapped onto two Bézier patches, a triangle, and very awkwardly onto a cube).  I also created a very simple scene editor, which lets you add new objects (triangles, cubes or patches) to the scene and move/rotate/scale them in the YZ, XY or XZ planes.

For a straightforward (unoptimized) software renderer, it runs pretty well on my Pocket PC.  If you’d like to test it without going through the trouble of checking out the project and compiling it, you can get the binary for a Pocket PC with an ARM processor here:

editor.exe (176 KB)  Read more...

Having a little extra time on my hands, and maybe a bit too much egg nog, I set out to write a basic 3D rendering system that can run under WindowsCE (or “Pocket PC” or “Windows Mobile” depending on how long you’ve had your WindowsCE device).  Attached is an ARM executable for your PPC that displays an animated tessellated Bézier Patch (optionally showing surface normals and mesh outlines).

mgraphics.exe (25.5 KB)

The code is also available on our public svn service.  Read more...

Nothing comes from nothing
Nothing ever could.
So, somewhere in my youth or childhood
I must have done something good.  Read more...

Lab49 has created a public repository for open source software projects.

I have a few projects up that I’d like to tell you about.  Read more...

If you can’t work with us, work like us.

Details inside …  Read more...

We recently had an internal presentation covering a variety of fundamental theories of computation that underly several important programming languages. Here are a few papers that might help explain those theories in more depth (if not the actual interpreters we developed):

• Foundational Calculi for Programming Languages
• Introduction to Lambda Calculus
• Making [Erlang] (Joe Armstrong’s PhD thesis)
 Read more...