Factor 0.81 now available

Download it from the Factor web site. Lots of new stuff in this release: FFI callbacks, multi-window UI, improved online help, and many updates to the contributed libraries. Also for the first time a pre-compiled Mac OS X (PowerPC) binary package is available! Just double-click on Factor.app and the Factor UI is started, no fuss.

Note that the detailed changelog is now part of the online help system, and so you can view it either from the Factor UI, or in the online documentation responder (as soon as I update the server on factorcode.org to 0.81, anyway).

New browser interface in the UI

Browser windows are what opens up when you click a presentation of an object.

I radically improved them today. Clicking a presentation inside a browser now re-uses the same window, and there is a history of previously-viewed objects. Also, a row of buttons across the top choose between multiple views of the object. This replaces the right-click command menu when clicking a presentation. Indeed, as strange as it sounds, I've removed support for popup menus from the UI altogether.

I also implemented help cross-referencing, analogous to the "calls out" (uses.) and "calls in" (usages.) features for words. You can now find out which articles link to the article you are reading now. This was made possible by implementing a small library to deal with directed graphs. I updated the word cross-referencing code to use this library too.

SCREENSHOT!

Windows UI backend complete

Doug Coleman has implemented a Windows backend for the Factor UI. I have been debugging X11 and Cocoa, and I implemented a new browser interface for looking at word definitions, reading documentation and inspecting objects.

I'm releasing 0.81 really soon now. I'll just wait for the UI overhaul to settle down, and work on documentation in the mean time.

X11 and Cocoa backends are (mostly) done

Today I spent a lot of time working on the X11 UI backend. First I fixed some bugs in GLX setup, then I added event handlers of various types, hooking up X11 input with UI gestures; mouse, keyboard, and close box. Now it appears that everything works. I also cleaned up and fixed a few remaining issues in the Cocoa backend.

Now my focus will shift to polishing the UI, writing documentation, and fixing bugs. Hopefully Doug will finish the Windows UI backend soon (he's making great progress), and I can release 0.81.

Objective C FFI now supports super message sends

While the Objective C FFI has had the ability to define subclasses for a while now, you were unable to call the superclass method from inside a subclass. Well now you can, for example consider the following definition of the FactorView class from the UI backend:

"NSOpenGLView" "FactorView" {
    ....
    { "initWithFrame:pixelFormat:" "id" { "id" "SEL" "NSRect" "id" }
        [
            rot drop
            SUPER-> [initWithFrame:pixelFormat:]
            dup "updateFactorGadgetSize:" add-resize-observer
        ]
    }
    
    { "dealloc" "void" { "id" "SEL" }
        [
            drop
            dup view close-world
            dup views get remove-hash
            dup remove-observer
            SUPER-> [dealloc]
        ]
    }
    ....
} { } define-objc-class

The addition of this capability makes the Cocoa interface feature-complete. I have been able to implement the missing parts from the UI backend, and modulo bugs, its pretty much done.

I'm very happy with the level of integration I've managed to achieve with the Cocoa binding. Factor can introspect Cocoa classes, define new Objective C classes, catch and throw Cocoa exceptions, and resend methods to the superclass. I'm not aware of any other concatenative language with such a comprehensive Cocoa binding.

So my main focus is now the X11 backend, and helping Doug implement the Win32 backend. The cool thing is, when this is all done, not only will Factor have a more powerful cross-platform UI, but also top-notch bindings for native graphics libraries which developers can call directly if they wish. I intend to document everything at all layers of the graphics subsystem.

Started X11 UI backend

The Cocoa backend is almost complete; it is missing a few features which depend on the ability to call methods on a superclass inside an Objective C method definition. Once I implement this feature, I can continue working on the Cocoa backend, but today, I decided to start the X11 backend instead. So far, I've moved the core of Eduardo's X11 bindings from contrib/x11/ to library/x11/, and cleaned up some of his utility words. I got it to the stage where a GLX window rendering Factor UI gadgets is displayed, however input does not work yet.

Here is my rough list of goals for Factor 0.81:

• Finish Cocoa and X11 UI backends
• Make the UI faster, write some new graphical tools
• Wait for Doug Coleman to finish the Windows UI backend :-)

Basically 0.81 is all about callbacks in the FFI, and the new super-duper platform-tuned UI.

Developing Factor has been a great educational experience for me. I taught myself many new things:

• The C language
• x86, PowerPC and AMD64 assembly
• OpenGL
• Cocoa (although my first exposure to Cocoa was a commercial gig, I still learned a lot more about Cocoa internals while writing the Factor Cocoa binding)
• X11 - learning it right now
• Language design and implementation techniques
• I even learned JVM bytecode so I could write the early JFactor compiler...

Partial continuations in Factor

Chris Double has posted another update about his work to implement partial continuations and generators in Factor. Cool stuff!

Cocoa backend for Factor UI in progress

I replaced the SDL code with a layered approach, right now consisting of a Cocoa backend only. I've also been refactoring the UI to support multiple windows. Here is a screenshot. The Cocoa code still needs a lot of work before it is stable. Once it is done, I will move on to the X11 backend.

Here is a roundup of the changes to the guts of Factor's UI over time:

• When I started working on the C library interface, the SDL library was the first library I wrote bindings for. I developed a few demos which rendered geometric shapes directly to the frame buffer.


• The first implementation of the graphical listener used the SDL_gfx library to render text. Later on I developed a complete SDL_gfx binding and with it developed a number of small graphics demos.


• I started work on the code which would become the UI, and implemented an SDL_ttf binding since I wanted decent-looking text rendering -- SDL_gfx only offered a single built-in 8x8 font.


• The SDL/SDL_gfx/SDL_ttf combo served as the backend for the UI for a long time.


• OpenGL bindings were contributed. Fed up with the low performance and limited features of SDL_gfx, I switched over to OpenGL rendering in Factor 0.79. I also rewrote the code calling SDL_ttf to use FreeType instead. SDL_ttf is a wrapper around FreeType.


• Now in Factor 0.81, I'm replacing SDL with Cocoa, X11 and Windows backends.

Computing connectedness of simplicial complexes

Every programmer is familiar with the concept of a graph. A graph can be thought of a set of vertices -- 0-dimensional simplices, and edges -- 1-dimensional simplices. If we keep going, a 2-dimensional simplex is a triangle, a 3-dimensional simplex is a pyramid, and so on, and we obtain a generalization of a graph known as a simplicial set.

Here are some simplices represented as arrays in Factor:

{ 0 }
{ 1 2 }
{ 1 2 3 }

We can consider "simplicial chains modulo 2". These are sets of simplices, with an "addition" operation defined as the set symmetric difference.

S{ { 1 } { 2 } } S{ { 2 } { 3 } } symmetric-diff .
S{ { 1 } { 3 } }

Given a simplex, such as { 1 2 3 }, we can compute its boundary by forming a chain of simplices of one lower dimension, simply by removing successive vertices from our simplex. For example,

{ 1 2 3 } (boundary) .
S{ { 1 2 } { 2 3 } { 1 3 } }

The boundary of a simplex is a simplicial chain. We can compute the boundary of a chain simply by computing the boundary of each simplex it contains, and then taking the sum.

S{ { 1 2 } { 2 3 } } boundary .
S{ { 1 } { 3 } }

We note that the boundary of a boundary is always the zero chain:

S{ { 1 2 3 } } boundary boundary .
S{ }

We call a chain a "cycle" if its boundary is the zero chain. Thus the boundaries are a subset of the cycles. The cycles which are not boundaries correspond to enclosed regions in the simplicial set which are not "filled in", since no higher-dimensional simplex has this region as its boundary.

Here is a more involved example. Here is a simplicial set which can be visualized as a hollow pyramid:

{
    { { 1 } { 2 } { 3 } { 4 } }
    { { 1 2 } { 1 3 } { 1 4 } { 2 3 } { 2 4 } { 3 4 } }
    { { 1 2 3 } { 1 2 4 } { 2 3 4 } { 1 3 4 } }
}

This set consists of four points, six line segments, and four faces. There are no simplices of higher dimension.

Intuitively, the four faces "enclose" a missing section in the middle, so we would like to say this space has one two-dimensional hole. On the other hand, there are no 1-dimensional holes, since any 1-cycle -- that is, any set of line segments whose boundary is empty -- forms the boundary of one or more faces of the pyramid, and thus the 1-dimensional space there is "filled in".

The notion of a homology module (or homology group) formalizes this notion in mathematics. The example presented above is the special case of simplicial homology modulo 2. Given a simplicial complex, we can compute a series of homology modules, indexed by positive integers, where each module has a "dimension". The dimension of the nth homology module is the number of n-dimensional holes in the simplicial complex.

I wrote a Factor program for computing homology. The algorithm is very naive, and will blow up with more than a dozen points or so. Later on I will make it much more efficient.

Here is the output, which computes homology of some small spaces:

0-dimensional holes correspond to connected components.
A path connected space has exactly one component (0-dimensional hole).
A 1-connected space is path connected and has no holes of dimension 1.
A contractible space is path connected, and has no holes of dimension 1 and higher.


==== One-point space - contractable:
 --> { { { 1 } } }
0-dimensional holes: 1


==== Two-point space (0-sphere) - not path connected, so not contractible:
 --> { { { 1 } { 2 } } }
0-dimensional holes: 2


==== Unit interval (1-disc) - contractible:
 --> { { { 1 } { 2 } } { { 1 2 } } }
0-dimensional holes: 1
1-dimensional holes: 0


==== 1-sphere - not 1-connected, so not contractible:
 --> { { { 1 } { 2 } { 3 } } { { 1 2 } { 2 3 } { 1 3 } } }
0-dimensional holes: 1
1-dimensional holes: 1


==== 1-disc - contractible:
 --> { 
    { { 1 } { 2 } { 3 } } { { 1 2 } { 1 2 } { 1 3 } } { 
        { 1 2 3 }
    }
}
0-dimensional holes: 1
1-dimensional holes: 0
2-dimensional holes: 0


==== 2-sphere - 1-connected but not contractible:
 --> { 
    { { 1 } { 2 } { 3 } { 4 } } { 
        { 1 2 } { 1 3 } { 1 4 } { 2 3 } { 2 4 } { 3 4 }
    } { { 1 2 3 } { 1 2 4 } { 2 3 4 } { 1 3 4 } }
}
0-dimensional holes: 1
1-dimensional holes: 0
2-dimensional holes: 1


==== 2-disc - contractible:
 --> { 
    { { 1 } { 2 } { 3 } { 4 } } { 
        { 1 2 } { 1 3 } { 1 4 } { 2 3 } { 2 4 } { 3 4 }
    } { { 1 2 3 } { 1 2 4 } { 2 3 4 } { 1 3 4 } } { { 1 2 3 4 } 
    }
}
0-dimensional holes: 1
1-dimensional holes: 0
2-dimensional holes: 0
3-dimensional holes: 0

Compiler status update, Cocoa subclassing

I've finished a compiler refactoring eliminating branch splitting. This has resulted in a slight performance decrease, which I hope to nullify by rewriting the low-level optimizer and code generation code.

My plan for the new low-level optimizer is to hold values in registers, and only "commit" them to the stack before leaving a basic block (by jumping to a word definition, for example). Already, enough infrastructure is in place so that words which are compiler intrinsics take inputs from registers, and store them back into regsiters. However, the current low-level optimizer is not very smart with this, and always generates stack load/store code before and after an intrinsic. The basic block optimizer then applies some rewrite rules, so that in some cases a sequence of the form "intrinsic, stack store, stack load, intrinsic" becomes "intrinsic, intrinsic". However, this is a rather crude hack, and it only catches a small number of cases. The correct fix, of course, is to not generate the redundant store/load and load/store sequences in the first place.

Since my last status update, I have also been debugging the FFI, callbacks, and the Cocoa bindings. All three are now in a state where I can actually subclass Objective-C classes from Factor, and, for example, render OpenGL in a NSOpenGLView subclass which overrides the drawRect: method.

Check out the crappy screenshot.

I will continue hacking away at the Cocoa bindings. At this stage, it appears that all that remains to be done before I can re-target the Factor UI to Cocoa is to write some nice wrappers for Cocoa event handling. I'm really looking forward to ditching SDL. Multi-window UI goodness!

Compiler reworking in progress

My most recent patches in the DARCS repository form the beginning of a major compiler reworking. Right now, most optimizations are disabled, so performance is not very good. As I update the optimizations for the new design and implement new ones, performance will improve beyond the level it was prior to starting this refactoring.

Originally I wanted to finish the Cocoa interface and implement the multi-window, native-backend UI in 0.81, however after hitting some bugs I decided to work on the compiler for a while instead.

My goals are several-fold:

• First, I want to fix a tricky bug in the branch folding optimization. Doing this properly seems to require changing the IR in some fashion.
• Second, I'm getting rid of unconditional branch splitting. Branch splitting is the process of converting
  

  A [ B ] [ C ] if D

  
  to
  

  A [ B D ] [ C D ] if

  
  In Factor 0.80 the compiler splits all branches, simplifying the IR and code generation by in some cases leading to an exponential increase in code size and compile time. Now branches will no longer be split. This requires changing code that traverses the IR.
• Consecutive math primitives should store intermediate values in registers where possible. Currently this is not really done very well at all. I want to improve this capability using a real register allocator, and also implement floating point intrinsics.
• I'm not sure I'll get this done for 0.81, but eventually I want to add a new 'complex float' type to the runtime. Instances of this type will be created automatically when a complex number is constructed from a pair of floats, and they will be represented efficiently; the two components will not be boxed. I plan on writing intrinsics for SSE2 and Altivec units on x86 and PowerPC, respectively, which operate on complex float values. This will be transparently integrated with the number tower and provide a performance boost for several benchmarks including Mandelbrot, and of course, any real code using complex floats.

I will probably release Factor 0.81 as soon as the new compiler implementation is working and offers comparable performance to 0.80. Factor 0.81 already offers enough in the form of new features; callbacks are a major step forward in terms of functionality. In 0.82, I will continue tweaking the optimizer to realize the full benefit of this refactoring, and then return to evolving the UI.