Sunday, September 02, 2007

Factor is now four years old

Time flies! I started working on Factor early September 2003. I can't believe that it has been this long already. I first announced Factor to the Internet in April 2004, after it had already been in development for some time. Here is the original announcement.

In the last year, we had a stready stream of releases, from Factor 0.84 to Factor 0.90, bringing many improvements to functionality, stability and performance. There are also several new contributors on board, which is great. While Factor 1.0 still seems far away, I feel that I'm making good progress and getting closer to achieving my goals.

Here are some code line counts:
  • Factor VM (written in C): 10285 lines
  • Factor core (written in Factor, core/ directory): 21016 lines
  • Factor libraries (written in Factor, extra/ directory): 58853 lines
  • Unit tests: 10101 lines
  • Documentation: 187405 words

Compared to the stats from last year, we see that:
  • the VM has only grown by 2000 lines (yet has evolved considerably in the time)
  • the core actually shrank because of better coding practices, and because the UI was moved out of the core
  • the amount of contributed libraries has more than doubled!
  • the documentation and unit tests have grown considerably too

I think this shows that we're moving in the right direction. I hope to release Factor 1.0 some time next year, and make it a 1.0 release worth the five year wait: an expressive language, with excellent performance, solid libraries, powerful tools and a robust implementation. And after I get a chance to build some large-scale applications with Factor and draw upon the experience gained, the language will continue to evolve into Factor 2.0. Watch out.

Saturday, September 01, 2007

Factor 0.90 now available

Factor 0.90 is now available. The web site hasn't been updated yet, so you can't browse the docs online right now; so instead just download it and read the docs in the UI!

Lots of changes:
Core
  • New module system. (Eduardo Cavazos)
  • Tuple constructors are defined differently now.
  • Mixin classes implemented; these are essentially extensible unions.
  • New float-array data type implements a space-efficient sequence of floats.
  • Moved <file-appender>, delete-file, make-directory, delete-directory words from libs/io into the core, and fixed them to work on more platforms.
  • New host-name word.
  • The directory word now outputs an array of pairs, with the second element of each pair indicating if that entry is a subdirectory. This saves an unnecessary stat call when traversing directory hierarchies, which speeds things up.
  • IPv6 is now supported, along with Unix domain sockets (the latter on Unix systems only). The stack effects of <client> and <server> have changed, since they now take generic address specifiers; see Networking.
  • The stage 2 bootstrap process is more flexible, and various subsystems such as help, tools and the UI can be omitted by supplying command line switches; see Command line switches for bootstrap.
  • The -shell command line switch has been replaced by a -run command line switch; see Command line switches for general usage.
  • Variable usage inference has been removed; the infer word no longer reports this information.
Tools
  • Stand-alone image deployment in tools.deploy vocabulary .
  • Stand-alone application bundle deployment on Mac OS X in tools.deploy.app vocabulary.
  • New vocabulary browser tool in the UI.
  • New profiler tool in the UI.
Extras
    Most existing libraries were improved when ported to the new module system; the most notable changes include:
  • asn1: ASN1 parser and writer. (Elie Chaftari)
  • benchmarks: new set of benchmarks.
  • cfdg: Context-free design grammar implementation; see http://www.chriscoyne.com/cfdg/. (Eduardo Cavazos)
  • cryptlib: Cryptlib library binding. (Elie Chaftari)
  • cryptlib.streams: Streams which perform SSL encryption and decryption. (Matthew Willis)
  • hints: Give type specialization hints to the compiler.
  • inverse: Invertible computation and concatenative pattern matching. (Daniel Ehrenberg)
  • ldap: OpenLDAP library binding. (Elie Chaftari)
  • locals: Efficient lexically scoped locals, closures, and local words.
  • mortar: Experimental message-passing object system. (Eduardo Cavazos)
  • openssl: OpenSSL library binding. (Elie Chaftari)
  • pack: Utility for reading and writing binary data. (Doug Coleman)
  • pdf: Haru PDF library binding. (Elie Chaftari)
  • qualified: Refer to words from another vocabulary without adding the entire vocabulary to the search path. (Daniel Ehrenberg)
  • roman: Reading and writing Roman numerals. (Doug Coleman)
  • scite: SciTE editor integration. (Clemens Hofreither)
  • smtp: SMTP client with support for CRAM-MD5 authentication. (Elie Chaftari, Dirk Vleugels)
  • tuple-arrays: Space-efficient packed tuple arrays. (Daniel Ehrenberg)
  • unicode: major new functionality added. (Daniel Ehrenberg)

Performance
  • The curry word now runs in constant time, and curried quotations can be called from compiled code; this allows for abstractions and idioms which were previously impractical due to performance issues. In particular, words such as each-with and map-with are gone; each-with can now be written as curry* each, and similarly for other -with combinators.
  • Improved generational promotion strategy in garbage collector reduces the amount of junk which makes its way into tenured space, which in turn reduces the frequency of full garbage collections.
  • Faster generic word dispatch and union membership testing.
  • Alien memory accessors are compiled as intrinsics where possible, which improves performance in code which iteroperates with C libraries.
Platforms
  • Networking support added for Windows CE. (Doug Coleman)
  • UDP/IP networking support added for all Windows platforms. (Doug Coleman)
  • Solaris/x86 fixes. (Samuel Tardieu)
  • Linux/AMD64 port works again.

A big thank you to all the contributors and testers who made this release possible.

Thursday, August 30, 2007

Partially redrawing an OpenGL scene in response to exposure events and state changes

Most OpenGL applications redraw the entire scene every time a refresh has to be performed. There are exceptions, however. For example, to maintain responsiveness and conserve CPU time, an UI toolkit should only redraw the gadgets which need redrawing, either as a result of exposure events or gadget state changes.

It seems that partial redraws together with double buffering are not well-documented or understood by OpenGL programmers. Since partial redraws are very important to the Factor UI, I'll document what I've learned so far in this blog entry.

Factor's UI always sets the viewport dimensions to the entire window, however a scissor rectable is set using glScissor() to clip rendering to the region being redrawn. Gadgets are always rendered to the back buffer. Once the exposed region has been redrawn, the problem is now to bring it into the front buffer.

The GLX spec does not state whether glXSwapBuffers() takes the scissor rectangle into account.

On some OpenGL implementations, for example the NVidia drivers on Windows, Mac OS X and Linux, the current scissor rectangle is taken into account, and so the Factor UI can just request that buffers be swapped, and this only copies the requested region to the front buffer.

On Windows machines with Intel 9xx graphics adapters, this does not work, and SwapBuffers() copies the entire back buffer to the front buffer. As I documented in yesterday's entry, there exists a special WGL API for copying a partial region of the back buffer to the front buffer. This appears to fix the problem.

On my Linux/PPC machine with an ATI Radeon 9200 card and the open source "radeon" driver built in to X.org, glXSwapBuffers() also ignores the back buffer. Now, the MESA OpenGL implementation used has an extension GLX_MESA_copy_sub_buffer() which adds a glXCopySubBufferMESA() function for copying part of the back buffer to the front buffer, however, this function is buggy! It works some of time, but other times makes the entire screen go black, or kills the X server altogether.

There is a general fallback routine for copying part of the back buffer, but this is sometimes slower than redrawing the entire scene, at least on the Linux/PPC box described above. You can use glCopyPixels() to copy pixels from the back buffer to the front buffer, after setting the destination with glRasterPos():
: gl-raster-pos ( loc -- )
first2 [ >fixnum ] 2apply glRasterPos2i ;

: gl-copy-pixels ( loc dim buffer -- )
>r fix-coordinates r> glCopyPixels ;

: swap-buffers-slow ( -- )
GL_BACK glReadBuffer
GL_FRONT glDrawBuffer
GL_SCISSOR_TEST glDisable
GL_ONE GL_ZERO glBlendFunc
clip get rect-bounds { 0 1 } v* v+ gl-raster-pos
clip get flip-rect GL_COLOR gl-copy-pixels
GL_BACK glDrawBuffer
glFlush ;

Note the fidgety calculations to convert Factor UI co-ordinates ((0,0) is top left corner) to OpenGL window co-ordinates ((0,0) is lower left corner).

I'm still unsure if SwapBuffers() respects the scissor region on other platforms and OpenGL implementations, and if not, what is the correct way to copy part of the back buffer to the front buffer in the fastest possible way.

One other solution I need to look into is finding a way to be notified when the back buffer becomes invalid. If we redraw only part of the back buffer, then call SwapBuffers() to flip the entire back buffer with the front buffer, then in many cases, the previous content in the back buffer is still valid. It becomes corrupt when the video card needs to reclaim 3D memory for other applications, though. If there was a notification when volatile image buffers become out of date, I could force a full redraw on the next refresh, even if only a few gadgets need to be redrawn.

Wednesday, August 29, 2007

C/C++

Every time you say "C/C++" and lump two very different languages together as one, you're telling the world that you don't know either language. Idiomatic C code is very different from idiomatic C++. Good C++ code has very little that is actually C. Even the problem domains they are used in are different. Usually "C/C++" comes up in Java apologist rants ("Java is unmaintainable you say? Well I spent 10 years chasing memory leaks in "C/C++", it was far worse!") however sometimes you see informed people saying "C/C++". Please, don't.

OpenGL redraw bug on Windows

A while ago, "glguy" reported an issue with Factor 0.89: the UI was not being redrawn properly on Windows. I borrowed a Windows laptop and reproduced the exact same issue, and it turns out both me and glguy have the same graphics adapter: an Intel Express GM915.

I found a workaround: if I disable double buffering and don't call SwapBuffers after redrawing the window, then the issue disappears, and furthermore, it appears as if double buffering is still performed!

This is really strange, and I don't think this workaround will work elsewhere, unless WGL always double buffers, and uses hardware page flipping if you explicitly ask for it, or something.

If anybody has UI redraw issues and they're not using this adapter, or not running Windows at all, let me know!

Update: I found the right fix. On Windows, the glSwapHintRectWIN function must be called before SwapBuffers when doing a partial redraw. Turns out this function is not necessary with most drivers, but Intel drivers are picky when it comes to this. Good to resolve this one, finally. The fix is in the darcs repository.

Tuesday, August 28, 2007

Units and reversable computation

Since we don't want space probes written in Factor to crash because of calculations on mismatching units, Doug Coleman wrote a units library:
10 feet 30 inches d+ 56 s d/

It can add, multiply and divide dimensioned quantities while converting on the fly and making sure all the units make sense (10 miles 30 teaspoons d+ is a runtime error).

There was one problem with this library though, and it was that converting a dimensioned quantity back to a scalar required some boilerplate; for example, we have the following code:
: inches ( n -- dimensioned ) 2.54 * cm ;
: inches> ( dimensioned -- n )
dup 0 { m } { } =dimensions?*
dimensioned-value 100 * 2.54 / ;

The inches word converts a number of inches to centimeters; cm in turn converts it to meters, which is the canonical representation of distances, then creates a dimensioned quantity. However the inches> word is ugly, and it is all boilerplate since the defintion of inches has all the required information.

Let's take a look at cm:
: cm centi m ;

And its auxilliary words:
: centi 100 / ;
: m ( n -- dimensioned ) { m } { } <dimensioned> ;

As you can see, <dimensioned> is the canonical constructor.

Now, enter Daniel Ehrenberg's inverse library. While Dan originally intended to use it for pattern matching, this library is a perfect fit for auto-generating words for converting dimensioned quantities back to scalars.

Indeed, out of the box, it cannot invert <dimensioned>, because it calls natural-sort which is not an invertible operation. However, we can explicitly define an inverse for <dimensioned> (not an inverse in the mathematical sense, since the original function is not one-to-one; strictly speaking, this is a section, that is, a function which satisfies only one of the two conditions of an inverse).

And now, everything works; here, undo is Dan's inversion combinator:
  100 cm [ inches ] undo .
5000/127

So 100 cm constructs a dimensioned object, after converting the dimension to canonical form (meters in the case of distance):
  100 cm .
T{ dimensioned f 1 { m } { } }

And [ inches ] undo takes a dimensioned quantity, and works backwards in order to obtain a number, which when passed to inches, would give the original quantity:
  [ inches ] undo .
5000/127

Lets take a look at the code generated by [ inches ] undo:
  [ inches ] [undo] .    
[ >dimensioned< { } =/fail { m } =/fail 100 * 127/50 / ]

It takes the dimensioned quantity apart, makes sure it is a distance (and not a time, etc), then multiplies the quantity itself by a conversion factor.

So we can convert a scalar represented by unit to any other unit in this way; we can also do stuff like:
  10 miles 30 km d+ [ yards ] undo .
19205600/381

What is shorter, a quarter of a mile or 400 meters?
  1/4 miles 400 m d< .
f

We also support compound units, such as miles per second, miles per second squared, etc. How many teaspoons in a liter plus a tablespoon?
  1 L 1 tablespoons d+ [ teaspoons ] undo .
77937/379

For volume units, the canonical representation is meters cubed:
  15 teaspoons .
T{ dimensioned f 379/5120000 { m m m } { } }

Here is a unit with a denominator:
  20 knots .
T{ dimensioned f 463/45 { m } { s } }

The inverse library automatically guards against invalid conversions:
  30 km 10 s d/ [ teaspoons ] undo .
Unification failed

This is seriously cool stuff. The implementation of units is very simple and elegant, too; only half of the code has to be written, because we can use inverse!

The inverse library depends on two things; the simple mapping between syntax and semantics (the composition of two functions is their concatenation, therefore the inverse of a concatenation of two functions is a concatenation of their inverses!) and it also depends on quotations being sequences rather than opaque code blocks. Two qualities which are unique to Joy dialects such as Factor.

HTTP server on factorcode.org

The Factor HTTP server on factorcode.org has been running non-stop since May 7th; that's almost 4 months. This site doesn't get a whole lot of traffic, but it seems that the I/O code and garbage collector are in good shape these days.