Sunday, October 30, 2005

Incompatible changes in Factor 0.79

Factor 0.79 is almost ready for release. There is a minor prettyprinter bug, and a show-stopper OpenGL failure on Windows that no doubt will be resolved soon. After that, I have to update the documentation, and it will be released. This release shakes things up a little, so I thought it would be worthwhile to post an entry about the most noticable changes, now that we have a number of active contributors.

First of all, the ifte combinator has been renamed to if.

Next up, literal syntax for various types has changed:

Data typeOld syntaxNew syntax
Vector{ 1 2 3 }V{ 1 2 3 }
ArrayNone{ 1 2 3 }
Hashtable{{ [[ key value ]] ... }}H{ [[ key value ]] ... }
Tuple<< class slots ... >>T{ class slots }
Complex number#{ real imaginary }#C{ real imaginary }

In particular, note that in 0.79, arrays play a much larger role in the language. Formely, arrays were an implementation detail; they lived in the kernel-internals vocabulary, did not perform bounds checking, and were only used internally to implement vectors and hashtables. In 0.79, arrays have a literal syntax, are fully safe, and live in the arrays vocabulary. Arrays are not resizable like vectors are, but are slightly more efficient. This is the only real difference; the same operations work on both, since Factor's sequences are fully generic. Arrays are now the preferred data type for literal sequences. In fact, literal vectors are extremely rare; there's really only two cases where they are needed:

V{ } clone -- make a new, empty vector
[ 1 , 2 , 3 , ] V{ } make -- implicit sequence construction

This is why arrays now have the old vector syntax, and vectors now have a slightly more verbose syntax.

In particular, these changes have made the inspector display much more readable.

Finally, I also wanted to touch on a topic that I have discussed on IRC, but never put in writing. Lists and conses are being phased out over time. This does not affect the upcoming release of 0.79, but eventually I hope that quotations can become a first-class immutable type with underlying array storage; they will reuse the [ ... ] syntax. Code that uses conses to store data will be refactored to use arrays and vectors instead. There are several reasons for this:
  • Conses entail a 2x space overhead, and make the inner interpreter needlessly slow as it traverses the 'cdr' pointer while interpreting code. While the compiler makes this irrelevant, not all code is compiled. During bootstrap, interpretation overhead accounts for a significant portion of run time.
  • If quotations become arrayed, first-class types, then the debugger will be radically improved, and return stack traces will become much more readable due to extra information available at run time. Anybody who has looked at :r output knows what I mean. Its hard to understand if it is just a quotation soup, without any idea of what word each quotation came from.
  • Conses require their own implementations of algorithms such as each, map, head, and so on. Already, some combinators like 2map are only implemented for arrays, and result in a quadratic performance degradation with conses. I realize the "iterator" design pattern is supposed to eliminate this type of duplication, but iterators have performance and complexity of implementation problems.
  • The Factor programming style, which tends to favor the creation of new sequences from old ones rather than direct mutation, virtual sequences, and using combinators instead of explicit recursion, does not really require conses. Most algorithms can be expressed effectively using arrays and vectors instead.
  • Factor's conses are already quite constrained by being immutable. Thus circular lists cannot be implemented, which the main application of conses that is difficult to achieve with arrays.
  • If a specific problem calls for conses, then nothing prevents anybody from implementing a library for working with them.
  • Removal of conses would remove the requirement for the object memory manager to handle headerless objects. This will allow switching to a generational mark-sweep-compact garbage collector, which uses less memory than the generational copying collector we have now. Also, giving each object a header allows incremental GC to be implemented.

The total removal of conses from the core library is quite a major change. However, to keep the language lean and mean, this is something that should be done. Some people might find it surprising that I am still considering major changes to Factor, even as it is more than two years old. However, I did not have the benefit of extensive research and experience in language design before I began this effort, so I'd rather streamline my design while I still can rather than accumulate a large body of historical cruft and scar tissue.

Friday, October 28, 2005

Factor 0.79 almost ready

Its been almost two months since Factor 0.78, but CVS is looking very good and its almost ready for release. I only have a few items on my list. Here is a screenshot showing off the working FreeType font rendering, and new GUI theme. The OpenGL rendering backend has improved performance considerably, however it is still not as snappy as I'd like. However, this will all get solved over time as the compiler matures, and we replace SDL with OS-specific windowing substrate.

Some other developments include Doug Coleman's extended math library, which adds many functions not provided in the core math library. This includes dimensioned units, combinatorial functions, polynomials, statistics, and number theory. Also, an X11 binding is in development. This will replace SDL on *nix platforms as the windowing substrate for the UI (except for OS X, which will use a Carbon binding that I will develop).

Sunday, October 23, 2005

Rendering text with FreeType and OpenGL

The port of the UI to OpenGL is almost complete. I have finished implementing the last major missing component, text rendering. Text is now drawn by calling FreeType directly; there is no SDL_ttf dependency any more. Each glyph is rendered to a display list that first draws a textured quad, and then translates the origin by the width of the glyph. This allows a string to be drawn simply by calling each glyph's display list in turn. Here is a screenshot:

Thursday, October 13, 2005

A random status update

First, hats off to Chris Double who continues to do cool stuff with his continuation-based web framework. His latest hack is a to do list web app that uses a capability-based security model. Instead of having to remember a username/password, you bookmark a randomly-generated URL.

Last week I acquired an Apple Mac. This has given me a chance to fix some long-standing problems in Factor on Mac OS X. I got the UI running, and I also fixed a couple of relocation bugs in the compiler.

I have also started overhauling the UI to use OpenGL for rendering instead of SDL. So far, I've implemented all graphics primitives except for text, developed a FreeType binding, and started writing on some code to display FreeType-rendered glyphs as OpenGL textures.

Moving to OpenGL will provide increased performance and better eye-candy, and is one step in my plan to get rid of SDL altogether. SDL has some annoying limitations, like only supporting one top level window, not providing any way to access the clipboard, and more. Instead of SDL, the UI will have platform-specific backends; the set I'm looking at so far is Carbon, X11 and Windows. I will personally develop the Carbon backend -- I ordered a book on this topic and it is coming in the mail. I might also do the X11 backend later if nobody else wants to. As for Windows, a couple of people have already expressed interest in helping out.

Here is a screenshot of what the OpenGL rendering looks like os far:

Not very pretty -- there is a rendering flaw with polygon outlines, and of course, text is missing.

Tuesday, October 04, 2005

Word name completion in listener, and quaternions

I added completion popups to the listener. Keyboard selection of possibilities has not been implemented yet. You have to use the mouse.

I also added support for quaternions to Factor's math library. Quaternions are useful for certain geometrical calculations; a 3-dimensional rotation around an axis can be represented as multiplication by a quaternion.

Quaternions are represented as pairs of real numbers. Literal syntax is Q{ a b c d }Q, where a, b, c and d are real numbers.

Many quaternion operations can be done using Factor's existing vector algebra words; this follows from the mathematical fact that the quaternions are a 2-dimensional vector space over the complex numbers:

Addition: v+
Subtraction: v-
Negation: vneg
Norm: norm
Multiplication by a complex number on the left: n*v

A few new words are also needed:

Convert complex number to quaternion: c>n
Multiply by a complex number on the right: q*n
Quaternion multiplication: q*
Quaternion division: q/
Quaternion conjugate: qconjugate

Sunday, October 02, 2005